\documentclass[11pt,a4paper,serbianc,oneside]{book}
\usepackage[utf8x]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{textcomp}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{ucs}
\usepackage{listings}
\usepackage[serbianc]{babel}
\usepackage{pdfsync}
\usepackage[left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage[ruled,noline,algochapter]{algorithm2e}



% Komanda za horizontal ruler
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}

%
% Definicija fiksiranih reci
%
\addto\captionsserbian{%
 \def\prefacename{Предговор}%
 \def\refname{Списак литературе}%
 \def\abstractname{Сажетак}%
 \def\bibname{Литература}%
 \def\chaptername{Глава}%
 \def\appendixname{Додатак}%
 \def\contentsname{Садржај}%
 \def\listfigurename{Списак слика}%
 \def\listtablename{Списак табела}%
 \def\indexname{Регистар}%
 \def\figurename{Слика}%
 \def\tablename{Табела}%
 \def\partname{Део}%
 \def\enclname{Прилози}%
 \def\ccname{Копије}%
 \def\headtoname{Прима}%
 \def\pagename{Страна}%
 \def\seename{Види}%
 \def\alsoname{Види такође}%
 \def\proofname{Доказ}%
 \def\glossaryname{Речник непознатих речи}
 \def\contentsname{Садржај}%
 }%

%
% Podesavanja paketa za listinge
%

\renewcommand{\algorithmcfname}{Алгоритам}


\renewcommand\lstlistingname{Листинг}
\lstset {
	basicstyle=\footnotesize\ttfamily,
	numbers=left,
	numberstyle=\tiny,
	%stepnumber=2,
	numbersep=5pt,
	tabsize=2,
	extendedchars=true,
	breaklines=true,
	keywordstyle=\color{blue},
	frame=b,
	stringstyle=\color{gray}\ttfamily,
	showspaces=false,
	showtabs=false,
	xleftmargin=17pt,
	framexleftmargin=14pt,
	framexrightmargin=3pt,
	framexbottommargin=4pt,
	framextopmargin=0pt,
	%backgroundcolor=\color{lightgray},
	showstringspaces=false
}

\lstloadlanguages {
	% Check Documentation for further languages ...
	%[Visual]Basic
	%Pascal
	%C
	%C++
	Java,
	XML,
	Bash,
	Python
}

%
% Podesavanje okvira listinga
%
\usepackage{color}
\usepackage{colortbl}
\usepackage{xcolor}
\usepackage{caption}
\usepackage{float}
\floatstyle{plaintop}
\restylefloat{table}
\DeclareCaptionFont{white}{\color{white}}
\DeclareCaptionFormat{listing}{\colorbox[cmyk]{0.43, 0.35, 0.35,0.01}{\parbox{\textwidth}{\hspace{12pt}#1#2#3}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white, singlelinecheck=false, margin=0pt, font={bf,footnotesize} }

%
% Pocetak dokumenta
%
\begin{document}

\input{naslovna.tex}


\tableofcontents
\newpage



\chapter*{Апстракт}


У модерним научним истраживањма постоји нераскидива веза између природних наука и информатике. Рачунари су доста утицали на развој науке у последњих 60 година.  Рачунарство високих перформанси је у велиој мери научницима олакшало истраживања и омогућило извршавање, до скоро, незамисливих анализа.

У овом раду ће се описати примена рачунарства високих перформанси у истраживању у области хемијске теорије графова. У истраживању је дефинисана и испитивана једна особина молекулских структурних дескриптора. За потребе истраживања је написан софтвер за извршавање на дистрибуираним рачунарским системима.

У првом поглављу је дат увод у хемијску теорију графова, дефинисани су структурни дескриптори и објашњена је њихова улога у хемији. Друго поглавље представља поставку проблема и алгоритам високог нивоа за добијање резултата.
У трећем поглављу је описана дистрибуирана платформа за извршавање софтвера и објашњено је које су предности њеног коришћења у истраживању.Четврто поглавље описује софтвер за решавање проблема са аспекта паралелизације, дизајна и оптимизације. У петом поглављу су представљени резултати добијени током истраживања. Шесто поглавље садржи анализу добијених резултата.





  



\newpage
\chapter{Увод у хемијску теорију графова}

\section{Графови и молекулски графови}

\subsection{Граф}
  


\textbf{Граф} $G$ је уређени пар скупова $V$ и $E$, што се пише $G=(V,E)$.  Елементи скупа $V$ су означени $v_1,v_2,v_3,...,v_n$ и сматраћемо да их има коначно много. Дакле, $V=\{v_1,v_2,...,v_n\}$, при чему $n$ означава број елемената скупа $V$. 
Елементи скупа $V$ се називају {\bf чворови} графа, док се $V$ назива скуп чворова.
Скуп $E$ садржи неке парове елемената скупа $V$, дакле неке парове чворова. Дакле, за нека два чвора, $v_r$ и $v_s$, може да важи $(v_r, v_s) \in E$. Парови који улазе у скуп $E$ одређују структуру одговарајућег графа. Елементи скупа $E(G)$ се називају \textbf{гране} графа $G$. 


Граф $G=(V,E)$ се дијаграмски приказује на следећи начин: За сваки од чворова графа (тј. елемента скупа $V$) нацртамо по један кружић (или велику тачку). Ако важи $(v_r,v_s)\in E$, онда кружиће који одговарају чворовима $v_r$ и $v_s$ спајамо линијом. Ако је, међутим, $(v_r,v_s)\not\in E$, онда одговарајуће кружиће не спајамо линијом. На Слици \ref{fig:graph} се налази дијаграмски приказ једног графа.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=25mm]{images/graph.png}
\end{center}
\caption{Дијаграм графа}
\label{fig:graph}
\end{figure}

Ако пар чворова $(v_r,v_s)$, припада скупу $E$, онда се за чворове $v_r$ и $v_s$, каже да су \textbf{суседни}. 

Једна од првих ствари које треба разјаснити јесте када су два графа иста (математички речено - изоморфна) а када различита. Графови $G$ и $G^*$ су \textbf{изоморфни} ако се њихови чворови могу обележити тако да су два чвора $v_r$ и $v_s$, суседна у графу $G$ ако и само ако су суедна у графу $G^*$. Kод иоле већих графова провера изоморфности представља јако тежак задатак, који до дан данас није решен на задовољавајући начин. На Слици \ref{fig:isomorph} се може видети пример два изоморфна графа.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=70mm]{images/isomorphic.png}
\end{center}
\caption{Изоморфни графови}
\label{fig:isomorph}
\end{figure}

Структурне формуле органских једињења добијају се тако што се сваки појединачни атом прикаже својим симболом ($C$ за угљеник, $H$ за водоник, $O$ за кисеоник,...). Ако између два атома постоји ковалентна хемијска веза, онда се између одговарајућих симбола повлачи црта (или две, односно, три црте ако се ради о двогубој, односно трогубој вези). Дакле, структурна формула молекула (односно хемијских јединњења) показује који парови атома су хемијски везани. Број хемијских веза које се завршавају у једном атому назива се валенца тог атома. 

Граф који одговара структурној формули назива се \textbf{молекулски граф} одговарајућег молекула. Постоје две врсте молекулских графова:плерограм и кенограм.

\textbf{Плерограм} се конструише тако што се сваки атом приказује чвором, а два чвора су суседна ако су одговарајући атоми хемијски повезани. Слика \ref{fig:plero} показује један плерограм и структурну формулу хемијског једњења  
представљеног тим плерограмом.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/plerogram.png}
\end{center}
\caption{Плерограм}
\label{fig:plero}
\end{figure}

\textbf{Кенограм} се конструише тако што се чворовима приказују сви атоми осим водоникових. На тај начин кенограм репрезентује само (угљенични) скелет органског молекула. Слика \ref{fig:keno} показује један кенограм и структурну формулу хемијског једнњења  
представљеног тим кенограмом.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/kenogram.png}
\end{center}
\caption{Кенограм}
\label{fig:keno}
\end{figure}


Истрживања у савременој хемијској теорији графова готово искључиво се врше на кенограмима. У литератури се, зато, 
често, говори о молекулским графовима, подразумевајући при томе кенограме. То ћемо надаље чинити и у овом раду.



\subsection{Оријентисани графови}

Скуп $E$ који дефинише гране графа може се конципирати и на други начин. Уместо да садржи неуређене парове, може се поћи од уређених парова. То значи да $(v_r, v_s)$ и $(v_s, v_r)$ представљају два различита ентитета, наравно уз претпоставку да је $r \not = s$. Тада се пар $(v_r, v_s)$ представља оријентисаном граном, која полази из чвора $v_r$ и завршава се у чвору $v_s$. Аналогно, пар $(v_s, v_r)$ се означава као оријентисана грана која полази из $v_s$ и завршава се у чвору $v_r$. Може се дозволити да истовремено постоје обе оријентисане гране. Графови са оваквим гранама називају се \textbf{усмерени графови} или \textbf{диграфови}. На Слици \ref{fig:digraph} је приказан дијаграм једног усмереног графа. 

\vspace{10mm}
\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=25mm]{images/digraph.png}
\end{center}
\caption{Дијаграм усмереног графа}
\label{fig:digraph}
\end{figure}



\subsection{За хемију значајне врсте графова}


Нека је $G=(V,E)$ неки граф. Број његових чворова означавамо са $n$ а број грана са $m$. С обзиром на број грана, постоје два екстремна случаја.


Ако граф нема ни једну грану, дакле ако је $m=0$, односно ако је $E$ празан скуп, онда говоримо о \textbf{празном} графу. У таквом графу уопште нема суседних чворова. 
 
Ако су у графу свака два чвора суседна, онда се ради о \textbf{комплетном} графу. Комплетни граф са $n$ чворова обележава се са $K_n$. Тај граф садржи $m=n(n-1)/2$ грана. Слика \ref{fig:kg} приказује један комплетан граф са 5 чворова.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=100mm]{images/kg.png}
\end{center}
\caption{Комплетан граф (K5) и цикл (C5)}
\label{fig:kg}
\end{figure}


Нека је $G$ граф. Граф добијен из $G$ када се из њега избаце неке гране и/или неки чворови, назива се \textbf{подграф} графа $G$. При томе се подразумева да ако избацимо неки чвор, онда избацујемо и све гране које се у том чвору завршавају. 

Нека је $k$ позитиван цео број. Нека је $G$ граф и нека су $v_0, v_1, v_2,...,v_k$ његови међусобно различити чворови, такви да је $v_0$ суседан са $v_1$, $v_1$ суседан са $v_2$,..., $v_{k-1}$ суседан са $v_k$. Тада се уређена $(k+1)$-торка чворова $(v_0, v_1, v_2,...,v_k)$ назива \textbf{пут} у графу $G$. Тај пут спаја чворове $v_0$ и $v_k$ и дужина му је $k$. 

Граф је \textbf{повезан} ако између било која два његова чвора постоји макар један пут. Ако граф није повезан, онда се он састоји из две или више компоненти, рецимо $G_1,G_2,G_3,...,G_p$, при чему за свако $i,j=1,2,...,p; i\not = j$, не посотји пут између било којег чвора графа $G_i$ и било којег чвора графа $G_j$. То ћемо писати овако: 
\begin{equation}
G=G_1\cup G_2 \cup G_3 \cup ... \cup G_p 
\end{equation}

Нека је $v$ чвор графа $G$. Број чворова који су (у графу $G$) суседни чвору $v$ назива се степен тога чвора. Обележавамо га са $\delta _v$. Ако сви чворови графа $G$ имају исти степен, онда је $G$ \textbf{регуларан} граф. Ако чворови регулараног графа $G$ имају степен $r$, онда је $G$ регуларан граф степена $r$. 

Повезани граф степена 2 назива се \textbf{цикл}. Цикл са $n$ чворова обележава се са $C_n$. За граф који као подграф садржи цикл кажемо да је цикличан граф.Ако садржи само један цикл онда је \textbf{уницикличан}. Код графова који садрже више од једног цикла ситуација је знатно сложенија. За граф чији цикломатични број $(= m-n+1)$ је $2,3$,... кажемо да је бицикличан, трицикличан,..., што, међутим, не значи да садржи само $2,3$,... цикла. Слика \ref{fig:kg} показује цикл са 5 чворова.


С обзиром на врсту циклова које садрже, графове делимо на бипартитне и небипартитне. Ако су сви циклови у графу парне дужине, онда је граф \textbf{бипартитан}. Графови који уопште не садрже циклове су такође бипартитни. Ако у графу постоји макар један цикл, непарне дужине, онда је граф \textbf{небипартитан}.


У теоријској хемији говори се о алтернативним и неалтернативним конјугованим угљоводоницима. За конјуговани угљоводоник кажемо да је \textbf{алтернативан} ако му је молекулски граф бипартитан. У супротном угљоводоник је \textbf{неалтернативан}.


Повезани граф који не садржи циклове назива се \textbf{стабло}. 

\subsection{За хемију значајни појмови теорије графова}

Нека граф $G$ има $n$ чворова и $m$ грана. Нека су $\delta _1,\delta _2,\delta _3,...,\delta _n$ степени његових чворова. Тада је 
\begin{equation}
\sum_{i=1}^n \delta_i = 2m  
\end{equation}

Из горе наведеног следи да у сваком графу укупан број чворова непарног степена је паран. Такође, долази се до закључка да регуларни граф непарног степена има паран број чворова.

Нека је $k$ цео број већи од 2. Нека је $G$ граф и нека су $v_1, v_2,...,v_k$ његови међусобно различити чворови, такви да је $v_1$ суседан са $v_2$, $v_2$ суседан са $v_3$, ..., $v_{k-1}$ суседан са $v_k$ и још $v_k$ суседан са $v_1$. Тада се уређена $k$-торка чворова $(v_1, v_k)$ назива \textbf{цикл у графу} $G$. Тада кажемо да је величина тог цикла $k$ и да је то $k$-члани цикл.

Молекулски графови полицикличних једнињења често садрже велики број циклова. Препознавање циклова у молекулским графовима, те одређивање њиховог броја је тежак задатак. Тај, наизглед једноставан проблем, није, до данашњег дана, решен нa ефикасан начин.

За повезани граф са $n$ чворова и $m$ грана, број $c$ дефинисан као 
\begin{equation}
c=m-n+1
\end{equation}
назива се \textbf{цикломатични} број. Оно што се у хемији конципира као "број прстенова" у једињењу је, у ствари, цикломатични број из теорје графова. У квантној хемији је веома рано установљено да $\pi$-електорнске особине конјугованих угљоводоника веома зависе од врсте циклова садржаних у молекулском графу.

Нека је $G$ граф, а $v_r$ и $v_s$, његова два чвора. Дужина најкраћег пута који повезује $v_r$ и $v_s$ назива се \textbf{растојање} чворова $v_r$ и $v_s$. Ову величину обележавамо са $d(v_r,v_s)$.

Две гране графа $G$ су \textbf{независне} ако немају заједничких чворова, тј. ако се не додирују. Број начина на који се у графу $G$ може изабрати $k$ међусобно независних грана означавамо са $m(G,k)$. При томе, договорно, узимамо да је за све графове, $m(G,0)=1$ и $m(G,1)=$ број грана графа $G$.

Било која колекција независних грана у графу $G$  назива се \textbf{спаривање}. Колекција од $K$ међусобно независних грана у графу $G$ назива се $k$-спаривање графа $G$. Према томе, $m(G,k)$, је управо број различитих $k$-спаривања графа $G$.

Нека граф $G$ има $n$ чворова и нека је $n$ паран број. Тада се свако $(n/2)$-спаривање графа $G$, ако такво постоји, назива \textbf{савршено} спаривање. Број савршених спаривања графа $G$, што је исто као $m(G,n/2)$, означавамо са $K(G)$. 


\subsection{Графови и матрице}

У овом одељку подразуменвамо да су чворови графа $G$ обележени са $v_1,v_2,...,v_n$. Овако означеном графу се могу придружити разне матрице. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=50mm]{images/11dmcp.png}
\end{center}
\caption{$1,1-$диметилциклопентан}
\label{fig:11dmcp}
\end{figure}

\textbf{Матрица суседства} $A=A(G)$ графа $G$ је квадратна матрица реда $n$, чији елемент $A_{i,j}$ на пресеку $i$-те врсте и $j$-те колоне је одређен на следећи начин:

\begin{equation} 
A_{i,j} =  \begin{cases} 
1 &\mbox{ако су чворови $v_i$, $v_j$ суседни; $i\not = j$} \\
0 &\mbox{ако чворови $v_i$, $v_j$ нису суседни; $i\not = j$} \\
0 &\mbox{ако је $i= j$ } \\
\end{cases} 
\end{equation}


На пример, матрица суседства молекулских графова $1,1-$диметилциклопентана, приказаног на Слици \ref{fig:11dmcp}, гласи:
\begin{equation}
A(G)=
\left[ \begin{matrix} 
0 &0 &1 &0 &0 &0 &0  \\ 
0 &0 &1 &0 &0 &0 &0  \\ 
1 &1 &0 &1 &0 &0 &1 \\ 
0 &0 &1 &0 &1 &0 &0  \\ 
0 &0 &0 &1 &0 &1 &0  \\ 
0 &0 &0 &0 &1 &0 &1  \\ 
0 &0 &1 &0 &0 &1 &0  \\ 
\end{matrix} \right]
\nonumber
\end{equation}


\textbf{Лапласова матрица} $L=L(G)$ графа $G$ је квадратна матрица реда $n$, чији елемент $L_{i,j}$ на пресеку $i$-те врсте и $j$-те колоне је одређен на следећи начин:

\begin{equation} 
L_{i,j} =  \begin{cases} 
-1 &\mbox{ако су чворови $v_i$, $v_j$ суседни; $i\not = j$} \\
0 &\mbox{ако чворови $v_i$, $v_j$ нису суседни; $i\not = j$} \\
\delta _i &\mbox{ако је $i= j$ } \\
\end{cases} 
\end{equation}

На пример, Лапласова матрица суседства молекулских графова $1,1$ - диметилциклопентана гласи:
\begin{equation}
L(G)=
\left[ \begin{matrix} 
1 &0 &-1 &0 &0 &0 &0  \\ 
0 &1 &-1 &0 &0 &0 &0  \\ 
-1 &-1 &4 &-1 &0 &0 &-1 \\ 
0 &0 &1 &2 &-1 &0 &0  \\ 
0 &0 &0 &-1 &2 &-1 &0  \\ 
0 &0 &0 &0 &-1 &2 &-1  \\ 
0 &0 &-1 &0 &0 &-1 &2  \\ 
\end{matrix} \right]
\nonumber
\end{equation}


Нека је граф $G$ повезан. Тада је његова \textbf{матрица растојања} $D=D(G)$ квадратна матрица реда $n$, чији елемент $D_{i,j}$ на пресеку $i$-те врсте и $j$-те колоне представља растојање између чворова $v_i$ и $v_j$. Матрица растојања $1,1$ - диметилциклопентана гласи:

\begin{equation}
D(G)=
\left[ \begin{matrix} 
0 &2 &1 &2 &3 &3 &2  \\ 
1 &0 &1 &2 &3 &3 &2  \\ 
1 &1 &0 &1 &2 &2 &1 \\ 
2 &2 &1 &0 &1 &2 &2  \\ 
3 &3 &2 &1 &0 &1 &2 \\ 
3 &3 &2 &2 &1 &0 &1  \\ 
2 &2 &1 &2 &2 &1 &0  \\ 
\end{matrix} \right]
\nonumber
\end{equation}


Свака од горе наведених матрица једнозначно одређује граф. Предност рада са таквим матрицама долази до изражаја када се користе рачунари. Матрица суседства је један од погодних и уобичајених начина да се информација о структури графа чува у меморији и даље процесира. 



Свака особина графа се може (мада не увек на једноставан начин) одредити одговарајућим алгебарским манипулацијама са матрицом суседства.

\subsection{Спектри графова}


Нека је $G$ граф са $n$ чворова и нека је $A(G)$ његова матрица суседства. Означимо са $I_n$ јединичну матрицу реда $n$.


\textbf{Карактеристични полином} графа $G$ задаје се релацијом:
\begin{equation}
\phi (G, \lambda) = det [\lambda I_n - A(G)]
\end{equation}

где $A(G)$ означава матрицу суседства. Карактеристични полином можемо писати и на следећи начин:

\begin{equation}
\phi (G, \lambda) = \sum_{k=0}^n a_k \lambda^{n-k}
\end{equation}

то јест као:

\begin{equation}
\phi (G, \lambda) = a _0 \lambda ^n + a _1 \lambda ^{n-1} + a _2 \lambda ^{n-2}+ ... + a _{n-1} \lambda + a _n
\end{equation}


при чему се $a_k$ назива $k-$ти коефицијент.


На основу елементарних особина детерминанти, $\phi(G,\lambda)$ је полином $n-$тог степена чија је променљива $\lambda$. Самим тим, једначина $\phi(G,\lambda)=0$ има тачно $n$ решења (не нужно међусобно различитих). У линеарној алгебри се доказује да су сва решења једначине $\phi(G,\lambda)=0$ реални бројеви. 


Нека су $\lambda _1, \lambda _2,...,\lambda _n,$ нуле карактеристичног полинома $\phi(G,\lambda)$ графа $G$ (решења једначине $\phi(G,\lambda)=0$). Тада се $\lambda _1, \lambda _2,...,\lambda _n,$ називају \textbf{сопствене вредности} графа $G$, a сви заједно \textbf{спектар} графа $G$.


Уобичајено је да се сопствене вредности графа нумеришу тако да је задовољен следећи услов:
\begin{equation}
\lambda _1 \geq \lambda _2 \geq \lambda _3 \geq ...  \geq \lambda _n 
\end{equation}


\textbf{Лапласов полином} графа $G$ задаје се релацијом:
\begin{equation}
\psi  (G, \lambda) = det [\lambda I_n - L(G)]
\end{equation}

где je $L(G)$ Лапласова матрица. Лапласов карактеристични полином се пише и на следећи начин:

\begin{equation}
\psi (G, \lambda) = \sum_{k=0}^n (-1)^k c_k \lambda^{n-k}
\end{equation}

то јест као:

\begin{equation}
\psi  (G, \lambda) = c _0 \lambda ^n - c _1 \lambda ^{n-1} + c _2 \lambda ^{n-2}- ... + (-1)^{n-1} c _{n-1} \lambda + (-1)^n c _n
\end{equation}


при чему за коефицијенте важи $c_k>0$.


Као и код обичног карактеристичног полинома, $\psi (G,\lambda)$ је полином $n-$тог степена чија је променљива $\lambda$. Jедначина $\psi (G,\lambda)=0$ такође има тачно $n$ решења: \begin{equation}
\mu _1 \geq \mu  _2 \geq \mu _3 \geq ...  \geq \mu  _n 
\end{equation}


Нека су $\mu  _1, \mu _2,...,\mu  _n,$ нуле Лапласовог карактеристичног полинома $\psi (G,\lambda)$ графа $G$. Бројеви $\mu _1, \mu _2,...,\mu _n,$ називају \textbf{Лапласове сопствене вредности} графа $G$, a сви заједно \textbf{Лапласов спектар} графа $G$.


\section{Стабла и хемијска стабла}

\subsection{Стабла}


Као што је већ напоменуто, повезани граф без циклова назива се стабло. 


\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=35mm]{images/rt.png}
\end{center}
\caption{Коренско стабло}
\label{ref:rt}
\end{figure}



\textbf{Усмерено стабло} је усмерен граф који би био стабло ако би се смерови грана игнорисали. Неки аутори ограничавају овај израз на случајеве када су све гране усмерене према одређеном чвору или од одређеног чвора.

Стабло се назива \textbf{коренским стаблом} ако се један чвор означи као корен, у ком случају гране имају природну оријентацију, према или од корена. На Слици \ref{ref:rt} се може видети један пример коренског стабла.

\textbf{Пут} $P_n$ је стабло са $n$ чворова у којем ниједан чвор нема степен већи од 2. \textbf{Звезда} $S_n$ је стабло са $n$ чворова у којем је један чвор суседан свим осталим чворовима, па самим тим има степен $n-1$. На Слици \ref{fig:pz} се могу видети примери звезде и пута са 5 чворова.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=110mm]{images/pz.png}
\end{center}
\caption{Звезда (S5) и пут (P5)}
\label{fig:pz}
\end{figure}


Стабла служе за графовску репрезентацију ацикличних молекула, нарочито алкана. У том случају граф одговара угљеничном скелету, а његови чворови репрезентују атоме угљеника. Јасно је, стога, да стабла којима приказујемо алкане не могу имати чворове чији је степен већи од четири.

Повезани граф без циклова, који не садржи чворове степена већег од 4, назива се \textbf{хемијско стабло}. 

Хемијска стабла су веома често објекти истраживања у хемијској теорији графова. Алкани, са тачке гледишта структурне хемије, су најједноставнија органска једињења. Садрже само две врсте хемијских веза: једноструке ковалентне везе угљеник-угљеник и ковалентне везе угљеник-водоник. Због тога је опис њихове електронске структуре релативно једноставан. Молекули алкана су скоро неполарни, што омогућава да се њихово физичко-хемијско понашање описује једноставним математичким моделима.

Хемијска стабла, која представљају математички модел алкана, спадају у графове са најједноставнијим особинама. Многи математички проблеми који се у случају свих (молекулских) графова тешко или никако не могу решити, имају допадљива решења у случају (хемијских) стабала. С друге стране, особине хемијских стабала нису уопште тривијалне и њихова истраживања доводе до резултата који су вредни и са математичке тачке гледишта. 

Због свих наведених разлога, математички модели који имају за циљ да повежу молекулску структуру са физичким, хемијским, фармаколошким и другим особинама хемијских једињења, по правилу се прво тестирају на алканима, уз примену хемијских стабала. То је поготово случај са структурним дескрипторима заснованим на графовима.



\subsection{Основне особина стабала}


У овом одељку ће бити наведене елемeнтарне особине стабала. Свака особина се може доказати одговарајућим математичким поступком \cite{gutman}. Дакле, за сва стабла, а самим тим и хемијска важе следеће особине:
\begin{itemize}
\item Стабло нема простих циклова, а прост цикл се добија ако се било било која нова грана дода у стабло.
\item Стабло је повезано, али ако се било која грана уклони из стабла, више неће бити повезано.
\item Свако стабло са више од једног чвора поседује чвор степена 1.
\item Стабло са $n$ чворова има $m=n-1$ грану.
\item Број чворова степена 1 у стаблу одређен је бројем чворова степена 3,4,..., на следећи начин:
\begin{equation}
n_1=2+n_3+2n_4+3n_5+...+(n-3)n_{n-1}
\end{equation}
\item Број чворова степена 1 у хемијском стаблу одређен је бројем чворова степена 3 и 4, на следећи начин:
\begin{equation}
n_1=2+n_3+2n_4
\end{equation}
\item Нека је $T$ стабло а $u$ и $v$ његова два чвора. Тада између $u$ и $v$ постоји један јединствени пут. 
\end{itemize}

\section{Молекулски структурни дескриптори}

\subsection{Општа разматрања}


Молекулски структурни дескриптори засновани на молекулском графу често се називају \textbf{тополошки индекси} \cite{gutman}. 

У вези са молекулским тополшким индексима морамо увек имати на уму следећи општи проблем. Молекулска структура је ненумерички појам, па се често не може у потпуности описати бројевима. С друге стране, у хемији, врше се мерења и сви мерни резултати се изражавају бројем. На тај начин, једној одређеној супстанци се могу придружити разни молекулски подаци, који одговарају њеним физичко-хемијским особинама. 

Једна од парадигми хемије је да су физичко-хемијске особине једињења условљена структуром молекула од којих се то једињење састоји. Трагање за везама између молекулске структуре (ненумеричког појма) и физичко-хемијских особина једињења (које су изражене бројем) јесте једно од основних циљева хемије као науке. 

Нека је $I=I(G)$ математички ентитет (број, матрица, полином, вектор, група,...) које се на неки начин придружује графу $G$. Ако је задовољен услов да за свака два изоморфна графа $G_1$ и $G_2$ важи $I(G_1)=I(G_2)$ онда се каже да је $I$ \textbf{инваријанта графа} или да је $I$ графовска инваријанта.

Треба обратити пажњу да из услова $I(G_1)=I(G_2)$, не следи да су графови $G_1$ и $G2$ изоморфни. Када би то био случај, онда би инвријанта $I$ потпуно одређивала структуру графа. Такава инваријанта до данас није откривена.

Графовске инваријанте са којима смо се до сада упознали су, између осталог: број чворова, борј грана, цикломатични број, број савршених спаривања, полином спаривања, карактеристични полином, спектар графа. Матрица суседства није инваријанта графа, јер њен конкретни облик зависи од нумерације чворова. Из истог разлога ни матрица растојања није инваријанта графа. 

Лако је вдиети да је број могућих графовских инваријанти бесконачно велик. Због тога нас, како у теорији графова тако и у хемијској теорији графова, занимају само неке погодно одабране инваријанте.

Показало се да се неке графовске инваријанте могу довести у везу са физичко-хемијским особинама молекула, и такве инваријанте се онда проучавају у хемијској теорији графова.  У почетку, негде до краја седамдестих година прошлог века, у хемијској литератури је био разматран сасвим мали број таквих инваријанти. Тада, међутим, број ових тополошких индекса починње нагло да расте, тако да данас има неколико стотина озбиљно разматраних, и много хиљада "предложених" тополошких индекса.

Да би се ова појава некако обуздала предложени су критеријуми за уврштавање једне графовске инваријанте међу легитимне молекулске структурне дескрипторе.

% Стави референцу на Балабана
Балабан је поставио следеће услове:

\begin{enumerate}
\item Добра корелација са физичко-хемијским особинама.
\item Низак степен дегенрације или потпуно одсуство дегенерације.
\item Лакоћа израчунавања.
\item Пораст са порастом разгранатости молекулског скелета.
\item Могућност да се модификује тако да буде применљив код незасићених једињења као и код једињења која садрже хетероатоме.
\end{enumerate}

Под \textbf{дегенерацијом} једног структурног дескриптора подразумева се појава да дескиптор има исту вредност за различите (неизоморфне) графове, Ако је $\zeta$  неки скуп молекулских графова, а $\iota$ неких скуп свих различитих вредности које инваријанта $I$ поприма у скупу $\zeta$, онда се степен дегенерације у скупу $\zeta$ може дефинисати као:

\begin{equation}
\delta = \frac{|\zeta| - |\iota|}{|\zeta| - 1},
\end{equation}

при чему $|\zeta|$ и $|\iota|$ означавају број елемената одговарајућих скупова. Ако сви графови из скупа $\zeta$ имају различите вредности за $I$, онда је $\delta = 0$, а ако сви графови имају исту вредност за $I$ онда је $\delta = 1$.


Рандић је формулисао следеће критеријуме:

\begin{enumerate}
\item Могућност непосредне структурне интерпретације.
\item Корелација са макар једном физичко-хемијском особином.
\item Могућност разликовања изомера.
\item Локална дефинисаност (то јест, дефиниција на основу структурних детаља везаних за чвор и/или грану и њихову непосредну околину).
\item Могућност да се уведе низ аналогних дескриптора "вишег реда".
\item Линеарна независност.
\item Једноставност.
\item Да није заснован на физичко-хемијским особинама.
\item Да није, на тривијлан начин, повезан са другим структурним дескрипторима .
\item Да се може ефикасно израчунати.
\item Да је дефинисан на основу лако разумљивих структурних концепата.
\item Да има коректну зависност од величине молекула.
\item Да се постепено мења при малим променама у молекулској структури.
\end{enumerate}


\subsection{Винеров индекс}

Нека је $G$ повезани граф. Збир растојања између свих парова чворова графа $G$ назива се \textbf{Винеров(Wiener)} индекс тога графа и обележава се са $W=W(G)$. 

Винеров индекс се сматра најстаријим молекулским структурним дескритпором, а чланак у ком је објашњен почетком примене структурних дескриптора у хемији.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=100mm]{images/34dmth.png}
\end{center}
\caption{3,4-диметилхексан}
\label{fig:34dmth}
\end{figure}


Помоћу математичких формула Винеров индкес се може задати на следеће међусобно еквивалентне начине:

\begin{equation}
W(G) = \sum_{r \le s} d(v_r, v_s) = \frac{1}{2} \sum_{r=1}^n \sum_{s=1}^n d(v_r, v_s) = \sum_{\{v_r, v_s\}\subseteq V(G) } d(v_r, v_s) 
\end{equation}

Ако са $D_{i,j}$ означимо $(i,j)$-ти елемент матрице растојања, онда је:

\begin{equation}
W(G)=\sum_{i<j} D_{i,j} = \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n D_{i,j}
\end{equation}

Нека је $G$ молекулски граф 3,4-диметилхексана, приказаног на Слици \ref{fig:34dmth}, и нека су му чворови означени као на слици. Тада важи да је $W(G)=68$, што се може закључити ако би се сабрали елементи који леже изнад главне дијагонале  матрице растојања

\begin{equation}
D(G)=
\left[ \begin{matrix} 
0 &1 &2 &3 &4 &5 &3 &4 \\ 
1 &0 &1 &2 &3 &4 &2 &3 \\ 
2 &1 &0 &1 &2 &3 &1 &2 \\ 
4 &3 &2 &1 &0 &1 &3 &2 \\ 
5 &4 &3 &2 &1 &0 &4 &3 \\ 
3 &2 &1 &2 &3 &4 &0 &3 \\ 
4 &3 &2 &1 &2 &3 &3 &0 \\ 
\end{matrix} \right]
\nonumber
\end{equation}

Нека је $d(G,k)$, број парова чворова графа $G$ чије је међусобно растојање једнако $k$. Јасно је да се међу елементима матрице суседства број $k$ појављује тачно $d(G,k)$ пута. 

Непосредно из дефиниције Винеровог индекса следи да је:

\begin{equation}
W(G) = 1 \times d(G,1) + 2 \times d(G,2) + 3 \times d(G,3) + ...
\end{equation}

то јест:

\begin{equation}
W(G) = \sum_{k \geq 1} k d (G,k)
\end{equation}

Претходни образац је интересантан јер се у њему не захтева да граф $G$ буде повезан. Тиме је омогућено дефинисање Винеровог индекса и за неповезане графове.

Тешко је набројати које су све хемијске, физичко-хемијске и фармаколошке особине органиских (а у новије време и неорганских) једињења биле доведене у везу са Винеровим индексом. У свом првом раду Винер је показао да се помоћу $W$ могу предвиђати тачке кључања алкана. У каснијим радовима показао је да се исто може учинити са топлотом изомеризације и топлотом испаравања, напоном паре, површинским напоном и индексом преламања. Такође, Винер је указао и на везу његовог индекса и међумолекулских сила, што је у пуној мери разрађено тек касније. 

Касније, у бројним радовима, показана је и применљивост Винеровог индекса за предвиђање густине, моларне запремине, индекса рефракције, вискозности, разних термохемијских величина (топлоте настајања, топлоте атомизације), критичне температуре и критичног притиска, брзине простирања звука, хроматографских ретенционих времена, како ацикличних, тако и цикличних, како алифатичних тако и ароматичних једињења, како угљоводоника тако и једињења са функционалним групама и хетероатомима \cite{gutman}.

Од мање стандардних примена могу се поменути одређивање просечне конформације алкана са дугачким угљениковим ланцима, разликовање изомера фулерена, опис механизма електроредукције, опис кристалних дефеката, а у најновије време предиђање константи равнотеже комплексних једињења. Објављене су и многе фармаколошке примене Винеровог индекса.


\subsection{Хасојин индекс}
Почетком седамдесетих година прошлог века Хасоја (Hosoya) је увидео значај једне комбинаторне особине органских једињења, о којој до тада нико међу хемичарима није размишљао. Иако се већ читав век знало да у органским молекулима постоје хемијске везе, и да између тих веза, нарочито између суседних, постоје некакве интеракције, тек је Хасоја почео да истражује односе који владају међу несуседним хемијским везама.


Ако се молекул прикаже својим уобичајеним молекулским графом $G$, онда је број начина на који се у том молекулу може изабрати $k$ међусобно несуседних угљеник-угљеник веза једнак броју $m(G,k)$ избора $k$ независних грана, односно $k$-спаривањаа у графу $G$. Са бројевима $m(G,k)$ смо већ упознати.


Укупан број спаривања у графу $G$, odnosno $\sum_{k \geq 0}m(G,k)$, назива се \textbf{Хасојин} индекс графа, и означава се са $Z=Z(G)$.


Треба имати у виду да сабирање почиње од $k=0$ и да је за сваки граф $m(G,0)=1$. Због тога увек важи да је $Z(G) \geq 1$.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=50mm]{images/stiren.png}
\end{center}
\caption{Стирен}
\label{fig:stiren}
\end{figure}


Из графа на Слици \ref{fig:stiren} видимо да је за молекулски граф стирена (или, што је исто, за молекулски граф етил-циклохексана) одговарајући Хасојин индекс има вредност 44, јер је $m(G,0)=1,m(G,1)=8,m(G,2)=19,m(G,3)=14,m(G,4)=2,m(G,k)=0$ за $k>4$.

За разлику од Винеровог индекса, готово све хемијске примене Хасојиног индкеса разрадио је Хасоја са својим сарадницима. У низи чланака који обухватају период од око 30 година, показано је да се поред тачке кључања алкана, Хасојиним индексом могу моделовати разни термодинамички параметри засићених угљоводоника, посебно ентропија, што се могло и теоријски доказати. Установљена је и веза између Хасојиног индекса и статичко механичког описа молекула \cite{gutman}. 


У другом низу радова $Z$ је примењен у теорији конјуговаих $\pi$-електронских система: на укупну $\pi$-електронску енергију, ред везе и расподелу наелектрисања. 

\subsection{Индекс повезаности}

Индекс повезаности увео је Рандић, па се он помиње и као Рандићев индекс повезаности. Као што је раније поменуто, $\delta_v$ означава степен чвора $v$.


\textbf{Индекс повезаности} графа $G$ је 

\begin{equation}
\label{eq:povezanost}
\chi = \chi(G)=\sum_{u,v} \frac{1}{\sqrt[]{\delta_u, \delta_v}}
\end{equation}
при чему се сабирање врши преко свих парова суседних чворова графа $G$.

Нема сумње да је, са тачке гледишта примена у хемији и фармакологији, индекс $\chi$ највише и најчешће примењивани молекулски структурни дескриптор. Један од разлога његове велике популарности је, свакако, што се $\chi$ добро корелира са разним молекулским особинама. Други разлог је што се $\chi$ лако израчунава и што за његово израчунавање није потребна иоле већа теоријска припрема. Трећи разлог је, што за разлику од Винеровог, Хасојиног и још понеког индекса, $\chi$ није цео него децималан број. Још један разлог за успех индекса повезаности је што се он релативно лако модификује за хетероатоме, те што постоје његове природне генерализације. 

Израз наведен у Обрасцу \ref{eq:povezanost} може се схватити као "индекс повезаности првог реда", $^1\chi$. Тада би индекс ``повезаности другог реда`` био:

\begin{equation}
^2\chi = ^2\chi(G) = \sum_{u,v,w}  \frac{1}{\sqrt[]{\delta_u, \delta_v, \delta_w}},
\end{equation}

где сабирање обухвата све путеве $P_3$ који се као подграфови садрже у графу $G$, при чему $u,v,w$ означава чворове који, тим редом, припадају путу $P_3$. На аналоган начин се уводе индекси повезаности трећег реда (сабирање преко свих подграфова $P_4$), четвртог реда (сабирање преко свих подграфова $P_5$), и вишег реда. Индекс повезаности нултог реда се тада природно одређује као:

\begin{equation}
^0 \chi(G)= \sum_v \frac{1}{\sqrt{\delta_v}}\ ,
\end{equation}
где се сабирање врши преко свих чворова графа $G$.

Најопштија генерализација израза \eqref{eq:povezanost} је следећа:
\begin{equation}
^{(H)} \chi (G)= \sum_H \frac{1}{\sqrt{\delta(H)}},
\end{equation}
где је $H$ неки подграф графа $G$, $\delta(H)$ је производ степена свих оних чворова графа $G$, који припадају подграфу $H$, а сабирање иде преко свих подграфова графа $G$, који су изоморфни графу $H$.

У случају да се атоми у посматраном молекулу разликују од угљениковог, модификације индекса повезаности (и његових управо описаних поопштења) врши се тако што се уместо степена чвора употребљава неки сложенији израз, коjи зависи од редног броја, електронегативности исл. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=100mm]{images/cicor.png}
\end{center}
\caption{Kорелација између тачке кључања и индекса повезаности}
\label{fig:cicor}
\end{figure}

Велика већина савремених примена индекса повезаности односи се на поопштења и модификације оригиналне формуле. Помоћу индекса повезаности моделоване су разноразне физичко-хемијске величине као што су енталпија кристалне решетке металних халида, тачка кључања алкохола и амина, брзина реакције дехидрогеновања халогено супституисаних угљоводоника, и анестетичко деловање хлоро-флуоро-супституисаних метана и етана. Такође, индекс карактерише обилна фармаколошка примена \cite{gutman}. 


На Слици \ref{fig:cicor} се може видети корелација између тачке кључања C2-C7 алкана и индекса повезаности $\chi$.





\subsection{Математичка истраживања индекса повезаности}

Индекс повезаности дефинисан је на тако једноставан начин да скоро и не постоји потреба да се испитује његова зависност од молекулске структуре. Због тога математички хемичари на њега дуго времена скоро и да нису обраћали пажњу. 

Промена је настала крајем прошлог века, када се мађарско-амерички математичар Ердеш заинтересовао за $\chi$. Он је доказао да међу свим повезаним графовима са $n$ чворова звезда $S_n$ има најмању вредност за $\chi$. Значај рада је у томе што је њиме показано да у вези са индексом повезаности постоје нетривијални, тешки и интересантни математички проблеми. До сада је у вези са индексом повезаности графова и молекулских графова добијено само неколико резултата. 

Ако је $G$ повезани граф са $n$ чворова онда је 
\begin{equation}
\sqrt{n-1} \leq \chi(G) \leq \frac{n}{2}.
\end{equation}

Најмању вредност за $\chi$ има звезда $S_n$, за коју је $\chi(S_n) \leq \frac{n}{2}$. Највећу вредност за $\chi$ имају сви графови чије су све компоненте регуларни графови. 

Ако је $T$ стабло са $n$ чворова, различито од звезде  $S_n$ и пута $P_n$, онда је:

\begin{equation}
\chi(S_n) < \chi (T) < \chi(P_n).
\label{eq:pz}
\end{equation}

Као што је већ речено $\chi(S_n) < \sqrt{n-1}$. Лако се показује да је $\chi(P_n) = \sqrt{2} + (n-3)/2$ за свако $n \geq 3$.

Једначина \ref{eq:pz} показује да је $P_n$ хемијско стабло са највећим индексом повезаности. Хемијска стабла са најамњим индексом повезаности су позната, али она нису јединствена. Постоји велики број стабала са истим, минималним индексом повезаности. Сва она су веома разграната.


\chapter{Струткурна осетљивост тополошких индекса}

\section{Глаткост хемијског индекса}

\subsection{Увод}


Као што је већ речено, тополошки индекс је нумеричка вредност повезана са хемијским саставом, која служи за одређивање корелације хемијске структуре са разним физичким особинама, хемијским реакцијама и биолошким активностима. Индекси који су базирани на молекулском графу су се показали као врло корисни, како у разним хемијским дисциплинама, тако и у многим другим областима. Данас постоји велики број таквих индекса. Код многих од њих, хемијска применљивост никад није била тестирана.

Познато је да је Рандић, између осталих, предложио критеријумe за уврштавање једног тополошког индекса међу легитимне молекулске структурне дескрипторе. Један од тих критеријума каже да је тополошки индекс валидан структурни дескриптор уколико се за малу промену молекуларне структуре вредност индекса мења постепено. Ова особина се назива \textbf{глаткост} хемијског индекса који се испитује. 

Иако потпуно разумљива и интуитивно прихватљива особина, глаткост хемијског индекса до данас никад није била испитивана. У овом раду је вршено истраживање које треба да попуни ту празнину.

\subsection{Квантификација глаткости}

Како би могли да квантификујемо глаткост тополошког индекса (и самим тим омогућимо упоређивање са другим индексима), уводимо две мере: струткурна осетљивост и максимални отклон \cite{boris}. Као предуслов за дефинисање ових појмова, треба објаснити процес генерисања скупа структурно сличних графова неком графу $G$.  

Нека је $G$ неки граф. Нека су $v_r, v_s$ и $v_t$ неки чворови графа $G$, такви да $(v_r, v_s)\in E(G)$ и $(v_r, v_t) \not\in E(G)$. Са $G'$ обележавамо граф који се добије уклањањем $(v_r, v_s)$ из $E(G)$ и додавањем $(v_r, v_t)$ у $E(G)$. За граф $G'$ кажемо да је настао минималном променом у графу $G$ (једна грана је замењена новом). 

Нека је $S(G)$ скуп графова. Скуп $S(G)$ правимо тако што прво претходном трансфромацијом $G \rightarrow G'$ генеришемо све могуће графове $G'$. Да би генерисани граф $G'$ додали у $S(G)$, он мора да задовољава следеће услове:
\begin{itemize}
\item $G'$ је повезан граф,
\item $G'$ није изоморфан са $G$,
\item $G'$ није изоморфан ни са једним елементом из $S(G)$.
\end{itemize}

Овако генерисан скуп $S(G)$ се може назвати \textbf{GED(G)=1 скупом}, тј. скупом графова чија је GED (\textit{graph edit distance}) вредност у односу на $G$ једнака 1. Верујемо да се овај скуп састоји од графова стуктурно најсличнијих графу $G$. Самим тим, разлика тополошког индекса графа $G$ и графа из $S(G)$ може да репрезентује осетљивост тополошког индекса на малу промену у графу. 


Сада можемо дефинсати следећи појам:


\textbf{Структурна осетљивост} индекса $TI$ у односу на граф $G$ је вредност:

\begin{equation}
SS(G) = \sigma(TI) = \sqrt{ \frac{1}{|S(G)|} \sum_{G' \in S(G)} (TI(G') - \mu(TI))^2 }
\end{equation}

где је: $|S(G)|$ број елемената скупа $S(G)$, $TI(G')$ вредност тополошког индекса који испитујемо за граф $G'$, а $\mu(TI)$  аритметичка средина вредности тополошких индекса свих графова у $S(G)$. Закључује се да $SS(G)$ представља стандардну девијацију у скупу вредности тополошких индекса за графове из $S(G)$.


Ако $SS(G)$ има високу вредност, онда претпостављамо да тополошки индекс $TI$ има мали или никакав значај. Ако, међутим, $SS(G)$ има ниску вредност, то и даље није гаранција да је индекс "валидан", јер вредност тополшких индекса може да буде хаотичан скуп. Да би ово проверили дефинишемо следећи појам:

\textbf{Максимални отклон} тополошког индекса $TI$ у односу на граф $G$ је вредност:

\begin{equation}
 Abr(TI, G) = \max_{G' \in S(G)} \bigg\vert TI(G') - TI(G)\bigg\vert .
\end{equation}

Оно што називамо максимални отклон, показује колико мала структурна промена у графу изазива велику промену у вредности испитиваног тополошког индекса. 

Са практичне тачке гледишта, најбоље је да су вредности за структурну осетљивост и максимални отклон довољно мале.


\subsection{Испитивани индекси}
У претходном одељку смо дефинисали начин на који је могуће квантификовати глаткост тополошких индекса. У овом раду фокусираћемо се на тополошке индексе засноване на степенима чворова графа, дакле индексе у облику:

\begin{equation}
TI(G) = \sum_{(u,v) \in E(G)} F(d_u, d_v)
\end{equation}
где је $E(G)$ скуп грана графа $G$, $u$ i $v$ чворови у графу $G$, $d_u$  и $d_v$ степени чворова $u$ и $v$, а $F$ функција(одређена тополошким индексом) над степенима чворова.


Познато је да на нумеричку вредност индекса заснованог на степенима чворова, највише утичу број чворова и број грана графа. Самим тим, логично је упоређивати разноразне вредности $TI$ за графове који имају исти број чворова и грана. У овом раду, разматраће се класе стабала са истим бројем чворова.

У Табели \ref{table:indices} дат је приказ индекса који ће бити испитивани.
\vspace{10mm}
\begin{table}[H]
\caption{Испитивани индекси}
\centering
 \begin{tabular}{l r}
Име индекса & Матеметичка дефиниција\\
\hline
 & \\
\textit{Randić}‎ & $R=\sum_{u,v \in E(G)} \frac{1}{\sqrt{d_u d_v}}$ \\
 & \\
\textit{First Zagreb} & $M1=\sum_{u,v \in E(G)} (d_u + d_v)$ \\
 & \\
\textit{Second Zagreb} & $M2=\sum_{u,v \in E(G)}(d_u d_v)$ \\
 & \\
\textit{Atom-bond connectivity} & $ABC=\sum_{u,v \in E(G)} \sqrt{\frac{d_u + d_v -2}{d_u d_v}}$ \\
 & \\
\textit{Sum-connectivity} & $SCI=\sum_{u,v \in E(G)}\frac{1}{\sqrt{d_u + d_v}}$ \\
 & \\
\textit{First geometric-arithmetic} & $GA1=\sum_{u,v \in E(G)}\frac{2\sqrt{d_u d_v}}{d_u + d_v}$ \\
 & \\
\textit{Augmented Zagreb} & $AZI=\sum_{u,v \in E(G)} \bigg ( \frac{d_ud_v}{d_u + d_v - 2} \bigg)^3$ \\
 & \\
\textit{Harmonic} & $HI=\sum_{u,v \in E(G)}\frac{2}{d_u + d_v}$ \\
\label{table:indices}
\end{tabular}

\end{table}

\section{Рачунарска имплементација израчунавања глаткости хемијског индекса}

\subsection{Алгоритам за израчунавање}
На основу дефиниција за израчунавање лако се закључује који кораци су потребни за добијање вредности $SS$ и $Abr$ за неки тополошки индекс. У сврху решавања проблема написан је софтвер који ће детаљније бити разматран касније у овом раду. Како смо већ описали поступак добијања $SS$ и $Abr$, Алгоритам \ref{alg:ssabbr}, описан псеудокодом, се намеће као валидно решење које треба софтверски имплементирати.
 
У  алгоритму, као улаз имамо променљиве $T(n), EI$ и $F$. Под $T(n)$ подразумевамо скуп свих неизоморфних стабала са $n$ чворова. $EI$ означава скуп имена индекса које испитујемо, a $F$ низ математичких функција које карактеришу одговарајући индекс. Резултат представља просечну вредност за $SS$ и $Abr$ у класи стабала задатој на улазу.

\vspace{1mm}
\begin{algorithm}[H]
 \KwData{$T(n), EI, F$}
 \For{$T\in T(n)$}{
 $S(T)=\emptyset$\;
  \For{$node \in V(T)$}{
  	\For{$ neighbor \in \{neighbor: (node, neigbor) \in E(T)\}$}{
  		\For{$nonneighbor \in \{noneighbor: (node, nonneigbor) \not\in E(T)\}$}{
  			$T' \leftarrow T$\;
  			 $ E(T') \leftarrow E(T) - (node, neigbor) + (node, noneighbor)$\;
  			\If{($T'$ is connected) \textbf{and} ($T' \not\cong T$) \textbf{and} $(\neg\exists T_s \in S(T) : T'\cong T_s)$ }{
				$S(T) \leftarrow S(T) + T'$  			
  			}
  		}
  	}
  }

  \For{$index$ in $EI$}{
    	 $TI_T = \sum_{(d_u, d_v) \in E(T)} F[index](d_u, d_v)$ \;
  	 \vspace{1mm}
  	 $TIvalues = \{\sum_{(d_u, d_v) \in E(S)} F[index](d_u, d_v): S \in S(T)\}$\;
  	 \vspace{1mm}
  	 $SS[index] [T] = \sigma (TIvalues)$\;
  	 $Abr[index] [T] = \max_{\; TI_v \;\in \; TIvalues} \bigg\vert TI_v - TI_T\bigg\vert$\;
  }
 }
 \For{$index$ in $EI$}{
  	 $AverageSS = \frac{\sum_{T\in T(n)} SS[index][T] }{|T(n)|} $\;
  	 $AverageAbr = \frac{\sum_{T\in T(n)} Abr[index][T] }{|T(n)|} $\;
  	 \vspace{1mm}
  	 \textbf{print} \textit{index, AveragaeSS, AverageAbr}
  } 

 
 
 \caption{Израчунавање структурне осетљивости и максималног отклона} 
 \label{alg:ssabbr}
\end{algorithm}

\subsection{Потреба за паралелизацијом}

Иако на први поглед алгоритам изгледа прилично једноставан за имплементирање, постоје ствари на које треба обратити пажњу. 

У Tабели \ref{tab:treenum} је дат преглед броја нeизоморфних стабала које алгоритам обрађује у зависности од броја чворова. Уочава се да број стабала интензивно расте са порастом броја чворова. 

Сада ћемо покушати приближно да одредимо комплексност описаног алгоритма за израчунавање глаткости тополошког индекса. Анализираћемо део који се односи на генерисање $GED=1(G)$ скупа. За остатак алгоритма вредности су очигледне. 

Пошто је познато да провера комплексности алгоритма не захтева строго прецизно израчунавање броја потрeбних операција, увешћемо нека уопштења. 

Обратимо пажњу на две $for$ петље које се извршавају при итерацији суседних и несуседних чворова неком одређеном чвору. Број ових итерација дакле представља број (не)суседа неког чвора, различит је у сваком пролазу и зависи од структуре стабла које се тренутно испитује. Није потребно знати тачан број тих итерација како бисмо одредили комплексност алгоритма. Ради упрошћења проблема, претпоставићемо да је број тих итерација сталан и да његова вредност одговара просечној вредности тачног броја итерација. Број тих итерација обележавамо $C_1n$ и $C_2n$ где су $C_1$ и $C_2$ неке константе, а $n$ број чворова стабла. Уочавамо да је $C_1 < 1$, $C_2 < 1$ . Оно што је битно уочити, јесте да број тих итерација зависи од $n$. Заиста, са повећањем броја чворова, повећава се број могућих (не)суседа неком чвору.

\begin{table}[h]
\centering
\caption{Број неизоморфних стабала}
\begin{tabular}{l r}
Број чворова & Број неизоморфних стабала\\
\hline
&\\
1& 1 \\
2& 1\\
3 &1\\
4 &2\\
5 &3\\
6 &6\\
7 &11\\
8 &23\\
9 &47\\
10 &106\\
11 &235\\
12 &551\\
13 &1,301\\
14 &3,159\\
15 &7,741\\
16 &19,320\\
17 &48,629\\
18 &123,867\\
19 &317,955\\
20 &823,065\\
\end{tabular}

\label{tab:treenum}
\end{table}

Сада ћемо анализирати део који се односи на додавање генерисаног стабла постојећем скупу већ изгенерисаних, неизоморфних стабала. Провера повезаности је проблем који има линерану комплексност и познато је да њему одговара $C_3n$ операција. Обратимо пажњу на део кода за проверу изоморфности. Овај део кода биће извршен само у случају да је изгенерисан граф повезан. Уопштавања ради, процентуални број изгенерисаних повезаних графова можемо сматрати сталним и обележићемо га са $C_4, C_4<1$.  Провере изморофности захтевају $C_5n$ операција. Oво на први поглед делује као лош избор, пошто је познато да алгоритам за израчунавање изоморфизма графова, у најгорем случају има комплесност $O(n!)$. Међутим, коришћењем посебних, оригинално уведених техника уз нека одређена ограничења, ово је изводљиво (касније ћемо објаснити на који начин).

Посматрајући алгоритам, долазимо до закључка да је број операција потребан за извршавање алгоритма:

\begin{equation}
|T_n|\cdot (n \cdot C_1n \cdot C_2n \cdot (C_3n + C_4C_5n ) +C_6n)+ C_7n  = C_0n^4 + C_8n,
\label{eq:numop}
\end{equation}
где је $|T_n|$ број стабала, $n$ број чворова стабла, $C_1n$ просечан број суседних чвоврова,  $ C_2n$ просечан број несуседних чворова, $C_3n$ број операција за проверу повезаности, $C_4$ процентуални број изгенерисаних повезаних стабала, $C_5n$ број операција за проверу изоморфности, $C_6n$ број операција за рачунање  $SS$ и $Abr$, и $C_7n$ број операција за рачунање просечне вредности $SS$ и $Abr$.

На основу  Једначине \ref{eq:numop}, уочавамо да алгоритам има комплексност $O(n^4)$. Нажалост, ово је прилично велика вредност. Једнопроцесорско извршавање серијскoг кода би трајало неприхватљиво дуго. Закључујемо да је писање паралелног кода једини валидан приступ за добијање резултата за стабла са иоле већим бројем чворова. 



Такође, уочен је и проблем недостатка физичке меморије за смештање података о свим стаблима 
са великим бројем чворова. Стабла су сачувана у, меморијски штедљивом, \textit{graph6} формату. И поред тога, компримовани подаци о стаблима заузимају меморијски простор величине и од неколико терабајта. За решавање овог проблема потребно је коришћење неког облика дистрибуираног фајл система.


\chapter{\textit{Hadoop} платформа за дистрибуирано програмирање}

\section{Увод у \textit{Hadoop}}
\subsection{Дигитални универзум}

Сваке године компанија EMC$^2$ организује истразживање под називом "Дигитални универзум" \cite{emc}. Циљ овог истраживања је анализа количине података који настану, реплицирају се и на неки начин буду искоришћени. У те податке спадају нпр. видео клипови на Јутјубу, слике на Фејсбуку, субатомски судари регистровани током истраживња у CERN-у, информације о банкарским трансакцијама, снимци телефонских разговора, снимци са безбедносних камера и много других информација. 

У истраживању из 2012. се може наћи доста интересантних чињеница, статистичких података и предвиђања, као нпр:

\begin{itemize}
\item Тренутно у свету постоји око 4 зетабајта(4*10$^{21}$ бајтова) информација. Предвиђа се да ће 2020. у свету бити 40 зетабајта информација
\item 2020. године 40\% информaција ће бити обрађивано на \textit{cloud} платформи
\item Број података који захтева заштиту расте много брже у односу на оне који не захтевају заштиту
\item Количина података коју појединици стварају о себи (писањем докумената, прављењем слика и сл.) је далеко мања од количине података који се стварају о њима од стране трећих лица
\end{itemize}


Оваква експанзија количине података на Интернету је највише утицала на фунцкионисање компанија попут Гугла и Јахуа, где се јавила потреба за разноразним анализама тих података. 2005. године, компанија Гугл је објавила архитектуру свог модела за дистрибуирано складиштење и паралелну обраду података у облику научног чланка. На основу тог модела, као део \textit{Apache Lucene} пројекта, настао је алат по имену \textit{Nutch}. Од \textit{Nutch}-a је касније развијен фрејмворк за дистрибуирано програмирање по имену \textit{Hadoop}.

\subsection{Hadoop}
Hadoop је фрејмворк отвореног кода за писање и покретње дистрибуираних апликација које процесирају велику количину података. Као кључне карктеристике фрејмворка могу се издвојити:

\begin{itemize}
\item \textbf{Робусност}. Hadoop се извршава на обичним, лако доступним рачунарима. Направљен је са претпоставком да се често дешавају кварови на оваквим машинама. Кварови се заобилазе без проблема у готово свим ситуацијама.
\item \textbf{Скалабилност}. Hadoop је дизајниран тако да има скоро линерану скалабилност.
\item \textbf{Једноставност}. Hadoop омогућава програмерима да врло лако пишу паралелни код, без обраћања пажње на интеракцију паралелних послова, мрежни трансфер података и слично.
\end{itemize}

Hadoop се састоји из две кључне целине: дистрибуираног фајл-система по имену {\textit{HDFS} и модела за паралелну обраду података по имену \textit{MapReduce}. У следећа два поглавља ће ове компоненте бити објашњене понаособ.



\section{Дистрибуирани фајл-систем}
\subsection{Концепти \textit{HDFS}-а}

Када неки скуп података постане већи од складишних капацитета једног рачунара, неопходно је поделити га и распоредити на више рачунара. Фајл-системи који управљају складиштењем података на више умрежених рачунара називају се \textbf{дистрибуирани фајл-системи}. Пошто су засновани на рачунарским мрежама, овакви фајл-системи имају један додатни ниво комплексности у односу на регуларне, локалне, фајл-системе. 

\textit{Hadoop} поседује свој дистрибуирани фајлсистем по имену \textit{\textbf{HDFS}(Hadoop Distributed FileSystem)}. \textit{HDFS} је фајл-систем дизајниран за складиштење огромних фајлова који се покреће на кластеру сачињеном од обичних, широкораспрострањених рачунара. Под појмом "огромних" фајлова подразумевамо фајлове величине неколико гигабајта, терабајта, па чак и петабајта.

\textit{HDFS} је оптимизован за системе где читања података има много више него уписа. Скуп података се копира или директно генерише на фајл-систему, а након тога се над њим врше разноразне анализе.

\textit{HDFS} не захтева никакве скупе хардверске платформе специјалне намене. Дизајниран је тако да може да се покреће на обичном хардверу, који је врло приступачан и јефтин. Код оваквих хардверских плтформи постоји велика вероватноћа појаве квара. \textit{HDFS} је направљен тако да ефикасно реагује при појави хардверских (а и софтверских) проблема.

\textit{HDFS} је дизајниран тако да ради са великом количином података, на уштрб брзине читања. Апликације које захтевају малу латенцу (реда десет милисекунди) током читања података, неће радити добро на оваквом фајл-систему.


\subsection{Интерфејс командне линије}

Крајњи корисник фајл-система практично и нема утисак да ради са дистрибуираним фајл-системом комлексне архитектуре. За интеракцију са фајл-системом направљен је командни интерфејс. Команде у великој мери подсећају на оне у Линукс оперативним системима. У Табели \ref{tab:hdfscli} дат је приказ основних команди за рад са фајл-системом. 

\bgroup
\def\arraystretch{1.5}
\begin{table}[H]
\caption{Преглед HDFS команди }
\centering
\begin{tabular}{l  r}
Команда &Опис\\
\hline
\texttt{cat} & Приказ садржаја фајла \\
\texttt{chmod} & Промена дозвола за рад са фајлом\\
\texttt{chown}& Променавласника фајла\\
\texttt{copyFromLocal} & Копирање фајла са локалног фајлсистема\\
\texttt{copyToLocal}& Копирање фајла на локални фајлсистем \\
\texttt{cp} & Копирање фајла\\
\texttt{ls} & Листање списка фајлова \\
\texttt{mkdir} & Прављење директоријума\\
\texttt{mv} & Премештање фајла\\
\texttt{rm} & Брисање фајла\\
\texttt{touchz} &Прављење празног фајла\\
\label{tab:hdfscli}
\end{tabular}

\end{table}
\egroup

\subsection{Струткура HDFS-а}


Физички диск карактерише \textbf{величина блока} - минимална количина података коју може да упише или прочита. Фајл-системи који раде над једним диском, управљају подацима на нивоу блокова, чија величина представља целобројни умножак величине блока физичког диска. Блокови фајлсистема су обично величине неколико килобајта, док је блок диска обично величине 512 бајтова. Све ово је, наравно, потпуно транспарентно за крајњег корисника фајл-система, који једноставно ради са подацима било које величине. 

У \textit{HDFS}-у такође постоји концепт блока. Овај блок је много већи од стандардног блока и његова величина је 64 мегабајта. Као у локалним фајлсистемима, фајлови у \textit{HDFS}-у су подељени на делове величине блока, који су физички сачувани као независни ентитети. За разлику од локалних фајл-система, фајл мањи од величине блока не заузима меморију величине блока.

Овако велики блокови су добри јер смањују време претраге. Последица овога је то да читање једног блока може да траје значајно дуже од његовог проналаска. 

Постојање апстракције блока за дистрибуирани фајл-систем има више предности. Фајлови могу бити већи од било ког физичког диска у мрежи. Код дистрибуираних фајлсистема блокови фајлова могу бити распорђени широм мреже. Блокови се добро уклапају у модел репликације, чиме се обезбеђују робустност и висок ниво приступачности података. Ради осигурња против физичког квара на диску или поремећаја у вредности блокова, сваки блок је ископиран на три различите локације. Невалидни и недоступни блокви се једноставно обезбеђују са неке алтернативне локације на начин који је транспарентан за корисника. 

Уочавамо два типа рачунара(чворова) у кластеру на ком се покреће \textit{HDFS}. У складу са \textit{master/slave} моделом то су: \textbf{\textit{Namenode}} и \textbf{\textit{Datanode}}. 

\textit{Namenode} обавља комплетно управљање фајлсистемом. Он чува информације о томе како су фајлови подељени у блокове и где су распоређени на мрежи (метаподаци). Такође, његова улога је да обезбеди отпорност система на грешке. Он повремено добија информације о целкуоном стању фајлсистема. У случају квара неког физичког чвора са подацима, овај чвор иницира репликацију података. За \textit{Namenode} је карактеристичан велики број улазно-излазних операција. Није пожељно да овај чвор обавља било какву другу функцију у кластеру. Проблем изазван важношћу \textit{Namenode-a} у систему, је то што са његовим кваром цео систем престаје са радом. Насупрот томе, физички или софтверски проблем осталих чворова фајл-система је лако премостив, јер и у том случају систем наставља са радом без икаквих проблема. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/HDFS.png}
\end{center}
\caption{\textit{HDFS} структура }
\label{fig:hdfs}
\end{figure}

Сви остали чворови у кластеру ће имати улогу \textit{Datanode}-а. Задатак ових чворова је директан рад са самим фајловима смештеним на физичком складишту. При упису или читању са дистрибуираног фајл-система, \textit{Namenode} усмерава клијента на одређене \textit{Datanode}-ове који управљају појединачним блоковима фајла. Клијент затим комуницира директно са \textit{Datanode}-ом ради процесирања локалних фајлова који одговарају блоковима. \textit{Datanode}-ови комуницирају међусобно ради репликације блокова.

У \textit{Hadoop} кластеру је могуће подесити \textbf{секундарни \textit{Namenode}}. Улога овог чвора је чување резервне копије метаподатака о фајловима на систему. У случају квара главног \textit{Namenode}-a, подаци са секундарног секундарни \textit{Namenode}-a се користе за опоравак система. 

На Слици \ref{fig:hdfs} можемо видети како изгледа структура једног HDFS кластера. Можемо уочити како је фајл подељен на блокове и како су блокови расподређени широм мреже. Такође, примећује се да је један блок копиран на више места. У случају квара једног \textit{Datanode}-a систем је у могућности да настави са радом без икаквих проблема. 


\subsection{Поређење HDFS-а са другим фајл-системима}

У овом делу ћемо у кратим цртама извршити упоређивање \textit{HDFS}-a са неким другим популарним дистрибуираним фајл-системима \cite{dfscomp}.

\begin{table}[h]
\centering%
\caption{Поређење \textit{HDFS}-a са другим системима}
\vspace{5mm}
\begin{tabular}{ l | l  l }
Карактеристика &   \textit{HDFS} &   Фајлсистем са \\
&   &   супротним приступом \\ 
\hline
&&\\
Архитектура&Централизована & Системи засновани на  \\
&  & \textit{DHT(Distributed Hash Table)}  \\
&  & моделу   \\    
&&\\
Конзистентност&Опоравак без прекида & \textit{Parallel virtual} \\
& & \textit{Filesystem (PVFS)}\\ 
&&\\
Комуникација&\textit{UDP} у некој & \textit{Google Filesystem (GFS)}\\ 
& будућој верзији& \\ 
&&\\
Конкурентност& Закључавање приступа & \textit{Parallel virtual} \\
& & \textit{filesystem (PVFS)}\\ 
&&\\
Безбедност&Без аутентификације& \textit{Sun Network} \\ 
& & \textit{filesystem (SNFS)}\\ 
&&\\
Перформансе&Рад са великим &\textit{Lustre}  \\ 
& фајловима,&\\ 
& лошије перформансе& \\ 
&&\\
Лиценца&Софтвер отвореног & \textit{Microsoft TidyFS}\\  
& кода&\\ 

\end{tabular}
\label{tab:dfscomp}
\end{table}



У Табели \ref{tab:dfscomp} је анализран HDFS са аспекта најважнијих особина које могу да карактеришу дистрибуирани фајл-систем, у које спадају:
\begin{itemize}
\item \textbf{Архитектура}.
Постоји више типова архитектуре дистрибуираног фајл система. Најчешће коришћена архитектура је базирана на \textit{master/slave} моделу. Такав фајлсистем се састоји из једног централног чвора за управљање системом, и осталим, радним чворовима. Насупрот томе, постоје децентрализоване, симетричне архитектуре, где се метаподаци о фајловима чувају на целом систему. Оваква архитектура је примењена код система заснованих на \textit{DHT (Distributed Hash Table)} моделу.

\item \textbf{Конзистентност рада}.
Битна карактеристика дистрибуираног фајл-система је подршка за такозвани \textit{stateless} режим рада. Код оваквих система  je омогућен опоравак од грешке без прекида рада целокуног система. Овакви системи су тежи за имплементацију. 
\item \textbf{Комуникација}.
Дистрибуирани фајлсистеми користе \textit{RPC (Remote Procedure Call)} методе за комуникацију, чиме постају независни од оперативног система и мрежних протокола.  Теоретски, фајл-системи могу да користе \textit{TCP} или \textit{UDP} протокол за мрежну комуникацију. Тренутно сви фајл-системи користе \textit{TCP} протокол.
\item \textbf{Конкурентност}.
При дизајну дистрибуираног фајл-система треба обратити пажњу на конкурентан приступ подацима. Неки системи врше закључавање приступа приликом читања податакa, док се код неких све операције врше синхроно.
\item \textbf{Безбедност}.
За приступ неким фајл-системима је потребна аутентификација (нпр. преко \textit{Kerberos}-a).  Насупрот њима, неки фајл-системи се потпуно ослањају на поверење између свих чворова и клијента. 
\item \textbf{Перформансе}.
Перфомрансе су врло битан фактор код избора дистрибуираног фајл-система. Неки фајл-системи имају лошије перформансе услед подршке за рад са оргомним подацима.
\item \textbf {Лиценца}
Основна подела по овом питању је на комерцијалне фајл-системе и фајл-системе отвореног кода који се у одређеној мери слободно могу користити и чијем развоју свако може да допринесе. 

\end{itemize}





\section{Модел за паралелну обраду података}

\subsection{\textit{MapReduce}}

Други кључни део \textit{Hadoop} фрејмворка, поред дистрибуираног фајлсистема, је модел за паралелну обраду података по имену \textit{MapReduce}.  Декомпозиција апликације у овом моделу није увек лака операција. Као највећа предност овог модела се истиче скалабилност. Након декомпозиције апликације, проширивање апликације на десетине и стотине параелних рачунара у кластеру је крајње једноставно. 

У \textit{MapReduce} моделу апликација се извршава у две фазе: \textbf{фаза мапирања} и \textbf{фаза редуковања}. Фрејмворк обично чита податке са фајл-система и обрађује их у фази мапирања. У фази редуковања, комплетан излаз из претходне фазе се обрађује ради добијања крајњих резултата. Најпростије речено, улога мапера је филтрирање и трансформација података и њихово прослеђивање сервису за редуковање који врши агрегацију над њима. 
  
Улазни подаци за апикацију морају бити задати у формату листе парова \textit{<кључ/вредност>}. Најчешћи случај коришћења апликације је обрада података из фајла. У том случају фрејмворк самостално процесира садржај фајла који желимо да анализирамо и апликацији као улаз прослеђује листу парова \textit{<редни број линије у фајлу / садржај линије>}. Могуће је и на многе друге начине форматирати улазне податке за паралелну апликацију. 

Изгенерисана листа парова је даље подељена на индивидуалне парове \textit{<кључ/вредност>}. Овај пар ћемо обележити са \textit{<k1/v1>}. Овај пар се процесира од стране \textit{map} функције у фази мапирања. У пракси се често \textit{k1} игнорише. Излаз ове функције, након трансформације, је листа парова \textit{<k2,v2>}. Трансформација је потпуно изолована, и њен резултат зависи искључиво од вредности \textit{<k1/v1>}.

\bgroup
\def\arraystretch{1.5}
\begin{table}[h]
\caption{Улазни и излазни подаци током извршавања \textit{MapReduce} апликације }
\centering
\begin{tabular}{l c c}
& Улаз & Излаз\\
\hline
Фаза мапирања &\textit{ <k1,v1>}& \textit{list(<k2, v2>) }\\
Фаза редуковања &\textit{<k2, list(v2)>} &\textit{list(<k3, v3>) }\\
\end{tabular}
\label{tab:mapred}
\end{table}
\egroup

Излазни резултат свих позива map функција се агрегира у једну велику, сортирану листу парова \textit{<k2,v2>}. Потом се од те листе прави нова листа парова, тако да су сви парови који имају исту вредност за \textit{k2} групишу пар \textit{<k2, list(v2)>}. У  фази редуковања се затим обрађује сваки од \textit{<k2, list(v2)>} парова појединачно и генерише листа парова \textit{<k3, v3>}. Као крајњи резултат фрејмворк скупља излазне податке из претходне фазе и уписује их у фајл на дистрибуираном фајл-систему.

Програми у \textit{MapReduce} моделу се обично пишу у \textit{Java} програмском језику. Међутим, коришћењем додатних библиотека, могуће је писати паралелне програме и у другим језицима као што су нпр.\textit{Ruby} и \textit{Python}.


\subsection{Како ради \textit{МapReduce}}

У претходном поглављу смо објаснили процес паралелне обраде података у \textit{MapReduce} моделу. Ради бољег разумевања модела, објаснићемо како фрејмворк у ствари обавља паралелну обраду података.

Јединица посла који клијент хоће да изврши у \textit{MapReduce} моделу, састављена од улазних података, извршне конфигурације и \textit{MapReduce} програма  се назива \textbf{посао}. Посао се дели на задатке, од којих постоје два типа: \textbf{задаци за мапирање} и \textbf{задаци за редуковање}. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/mrstruct.png}
\end{center}
\caption{MapReduce структура}
\label{fig:mapred}
\end{figure}

Постоје два типа чворова у систему који контролишу извршавање посла. То су \textit{\textbf{Јobtracker}} и \textit{\textbf{Тasktracker}}. Један чвор има улогу \textit{Јobtracker}-a, и он координира послове на систему, тако што распоређује задатке на \textit{Тasktracker}-има. \textit{Tasktracker}-a има више, они извршавају задатке и шаљу извештај о напретку \textit{Jobtracker}-у, који на тај начин прати напредак извршавања послова. Уколико дође до проблема при извршавању задатка, он бива прераспоређен на неки други чвор. На Слици \ref{fig:mapred} се може видети структура \textit{MapReduce} система.

Улазни подаци који се обрађују се раздвајају на делове фиксне величине. За сваки од тих делова се ствара по један задатак за мапирање, који покреће функцију за мапирање дефинисану од стране корисника. Функција за мапирање обрађује један по један елемент у делу података који је прослеђен задатку за мапирање.

Уколико су улазни подаци подељени на много мањих делова, време потребно за обраду једног дела је мало у односу на време потребно за обраду свих улазних података. Kод паралелне обраде великог броја делова улазних података, балансирање оптерећења процесорске снаге је на врло добром нивоу, пошто ће бржи рачунар бити у стању да обради више делова током извршавања послова од споријег рачунара. С друге стране, ако су делови превише мали, време потребно за управљање задацима постаје доминантно у осносу на време за извршавање самог посла. За већину послова, пожељно је да величина јендог дела за обраду буде иста као величина блока у фајл-систему. 

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/mrflow.png}
\end{center}
\caption{Ток паралелног извршавања апликације}
\label{fig:mrflow}
\end{figure}
 
Задаци за мапирање се, уколико је могуће, заказују за извршавање на чвору на ком се налази део података у дистрибуираном фајл-систему, који он треба да обради. Уколико су заузета све три чвора на којима се налазе реплике блокова за обраду, задаци се заказује на неком слободном чвору, што резултира трансфером података преко мреже. Сада је јасно зашто је оптималан део за обраду података идентичан величини блока у фајлсистему. Уколико би део за обраду био нпр. дупло већи од блока, велика је вероватноћа да ће мрежни трансфер података бити неопходан.

Излазни подаци задатка за мапирање се сортирају и групишу по заједничком кључу. Ови подаци се не уписују на дистрибуирани фајл-систем, већ на локални диск. Пошто су ово привремени подаци који се одбацују након обраде од стране задатака за редуковање, њихово снимање на дистрибуирани фајлсистем са све репликацијом је потпуно непотребно. Цена овога је да се задатак за мапирање поново покреће уколико се на неки начин ови подаци изгубе или поремете пре него што се прикупе од стране задатка та редуковање. На Слици \ref{fig:mrflow} се може видети горе описани ток паралелне обраде података.

Задаци за редуковање немају предност читања локалних података, пошто се подаци за овај задатак скупљају са више места у мрежи, и агрегирају тамо где се задатак извршава. Излазни подаци задатка за редуковање се уписују на дистрибуирани фајлсистем, тако да се једна реплика блока уписује на самом месту изршавња задатка, чиме се смањује трансфер података преко мреже.

Број задатака за редуковање не зависи од величине улазних подтака, већ се задаје независно. Кад има више задтака за редуковање, излазни подаци задатака за мапирање се групишу тако да се за сваки задатак за редуковање прави једна партиција података. Сви подаци са истим кључем су наравно у једној партицији. 


\subsection{Упоређивање \textit{MapReducе}-а са класичним кластер приступом}

У овом делу ћемо објаснити разлику између \textit{MapReducе}-а и класичног кластер приступа 
\cite{hadoop}. 

Паралелни прорачуни се већ дуже време обављају на \textit{HPC} кластерима и \textit{Grid}-овима коришћењем разних метода. Најчешће коришћен интерфејс за паралелну обраду података је \textit{MPI (Message Passing Interface)}. Најпростије речено, овај приступ у рачунарству високих перформанси се заснива на дистрибуирању послова на више рачунара у кластеру, који приступају неком заједничком фајл-систему. Овај модел је добар за послове који су захтевни по питању процесорске снаге. Проблем овог приступа настаје код обраде великих података, пошто мрежни проток знатно утиче на перформансе програма.

Насупрот овоме, \textit{MapReduce} покушава да распореди податке и послове тако да читање података за обраду буде локализовано што је више могуће. \textit{MapReduce} је имплементиран тако да се, у ствари, пропусни опсег мреже сматра најбитнијим ресурсом у кластеру.

\textit{MPI} даје велику контролу програмеру, али захтева експлицитно управљање протоком података коришћењем \textit{C} рутина ниског нивоа. Алгоритми за паралелизацију мање-више нису стандардизовани. \textit{MapReduce} ради на много вишем нивоу. Програмер једноставно ради са паровима кључева и вредности и уопште не брине о протоку података.

Управљање делимичним кваровима на кластеру током извршавања \textit{MPI} посла је изазован проблем. \textit{MapReduce} потпуно изолује корисника од овог проблема тако што се послови извршавају конзистентно без обзира на евентуални проблем. Ово је могуће јер су задаци за мапирање/редуковање потпуно независни. 

\textit{MapReduce} делује као програм који више ограничава корисника, што је у неком смислу и тачно, јер је корисник лимитран на рад са кључевима и вредностима и предефинисан механизам координације задатака за мапирање и редуковање. Ипак, не постоји много проблема који се не могу прилагодити овом приступу. Звучи изненађујуће да у проблеме које је могуће изразити преко \textit{МapReduce}-a спадају алгоритми за анализу слика, графовски прорачуни, машинско учење, итд. Међутим, треба нагласити да је примарна намена \textit{MapReduce}-a паралелна обрада великих података.


\chapter{Софтвер за израчунавање глаткости индекса}

\section{Паралелизација и домен декомпозиција}

\subsection{Увод}
Као што смо већ објаснили, алгоритам за израчунавање глаткости има комплексност $O(n^4)$, па је за добијање жељених резултата за велике графове неопходно писање паралелног кода. \textit{Hadoop} се истиче као добра платформа за извршавање паралелног програма из два разлога: 
\begin{itemize}
\item Скуп графова које треба обрадити се смештају у фајлове величине и до неколико терабајта. Уочавамо да је \textit{HDFS} добро решење.
\item \textit{MapReduce} је једноставан модел за паралелизацију. Програмер \textit{MapReduce} апликације не мора да води рачуна о проблемима на ниском нивоу. 
\end{itemize}

Избор платформе није довољан услов за ефикасно добијање резултата. Могуће је уочити велику разлику у брзини извршавања програма при примени различитих алгоритама и метода парелелне декомпозиције.

За имплементацију нашег решења коришћен је програмски језик \textit{Python}. \textit{Python} је изабран првенствено због \textit{NetworkX} библиотеке за рад са графовима, написане за тај језик \cite{networkx}. \textit{NetworkX} је вероватно најкомплетнија постојећа библиотека за рад са графовима. Употреба ове библиотеке је доста утицала на брзину развоја софтвера.

На Слици \ref{fig:mymr} се може видети на који начин је извршена паралелизација алгоритма за израчунавање глаткости. Детаљније објашњење следи у наредним одељцима.

\begin{figure}[htp]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/MyMR.png}
\end{center}
\caption{Паралелно извршавање софтвера}
\label{fig:mymr}
\end{figure}


\subsection{Улазни подаци}


Као улазне податке за наш проблем смо одабрали класу стабала са истим бројем чворова, $n$.
За генерисање улазних податка је коришћен алат \textit{geng} из \textit{nauty} пакета за рад са графовима \cite{nauty}. Једна од многих фунцкионалности овог алата је генерисање скупа неизоморфних графова по задатим критеријумима. Примера ради, класа стабала са 10 чворова се генерише командом:

\begin{lstlisting}[language=bash, frame=none, numbers = none]
geng -cbf 10 9
\end{lstlisting}
чиме смо скуп графова ограничили на повезане(\textit{c}), бипартитне (\textit{b}), ацикличне (\textit{f}) графове са 10 чворова и 9 грана. 

Графови генерисани \textit{geng} алатом налазе се у \textit{graph6} формату. Граф се представља у овом формату на следећи начин \cite{nauty}: 
\begin{enumerate}
\item Горњи троугао матрице суседства се запише као бит вектор дужине $n(n-1)/2$, тако што се редом додају вредности матрице:
 $[0,0]$, $[0,1]$, $[0,2]$,..., $[0,n]$, $[1,1]$, $[1,2]$, $[1,n]$,..., $[n-1,n]$. Претпоставимо да је тај бит вектор записан у облику 100010110001110.
\item Додајемо нуле на крај, тако да укупан број битова буде дељив са шест. У нашем примеру додајемо три нуле и сада имамо бит вектор 100010110001110000. 
\item Бит вектор делимо у групе по 6 битова. Добијамо 100010 110001 110000.
\item Сваки скуп битова претварамо у декадни систем и додајемо вредност 63. Добијамо 97 112 111. 
\item Испред ових вредности додајемо број вредност која одговара броју чворова графа увећану за 63. Добијамо 69 97 112 111.
\item Сваки од ових бројева представимо одговарајућим карактером из \textit{ASCII} кода. Добијамо вредност \textit{Еаpo}.
\end{enumerate}

Примећујемо да овако сачуван граф заузима $1+ceil((n(n-1)/2)/6)$ битова. Фајл који садржи улазне податке дакле садржи низ стрингова који предстљављају графове у \textit{graph6} формату.


\subsection{Мапирање}

Сваки задатак за мапирање треба да добије одређен број графова за обраду. Предефинсано понашање \textit{MapReduce}-a је такво да задаци добијају по 64 мегабајта(величина блока у фајл-систему) података за обраду. За прецизну контролу могуће је користити постојећу класу \textit{NLineInputFormat} као улазни формат, како би тачно одредили колико линија улазног фајла(број графова) свак задатак за мапирање треба да обради.

Задатак за мапирање треба да ишчита један по један граф са стандардног улаза, да га парсира, изгенерише одговарајућу \textit{GED=1} групу, и за сваки тополошки индекс који испитујемо израчуна структурну осетљивост и максимални отклон за тај граф. О самој имплементацији ових акција биће речи касније. Такође, рачуна се и вредност тополошког индекса за улазне графове. Листинг \ref{lst:SCM} садржи један сегмент имплементације овог задтка.

Након израчунавања свих вредности за структурну осетљивост и максимални отклон, резултати на задатку за мапирање се сортирају и групишу по заједничком кључу, што би у овом случају био тополошки индекс.

\begin{lstlisting}[language=Python,caption=smoothnessCalculationMapper.py, label=lst:SCM]
topologicalIndexes = []
for function in [R, M1, M2, ABC, SCI, GA1, AZI, HI]:
    topologicalIndexes.append(TopologicalIndex(function))
treeThumbprintGenerator = TreeThumbprintGenerator()
ged1GroupGenerator = GED1GroupGenerator(treeThumbprintGenerator)
for graph6Graph in stdin:    
    graphGroup = GraphGroupMath()
    graph = parse_graph6(graph6Graph.strip())
    for ged1Graph in ged1GroupGenerator.generateGED1GroupOld(graph):
        graphGroup.addGraph(ged1Graph)     
    for topologicalIndex in topologicalIndexes:
        tiValues = graphGroup.calculateTi(topologicalIndex)
        stdev = graphGroup.calculateStandardDeviation(topologicalIndex) if graphGroup.count() > 1 else float("NaN") 
        diffs = graphGroup.calculateTiDiffs(topologicalIndex, graph)
        print "%s\t%f %f %f" % (topologicalIndex.name(), stdev,max(diffs), topologicalIndex.value(graph) )
 \end{lstlisting}

\subsection{Редуковање}

Задатак за редуковање ће добити све вредности (прикупљене од свих задатака за мапирање) за структурну осетљивост и максимални отклон за један или више тополошких индекса. Овај задатак рачуна просек вредности улазних података на нивоу једног индекса. Такође, рачунају се и минимална и максимална вредност тополошког индекса за улазне графове. Листинг \ref{lst:SCR} садржи један сегмент имплементације овог задатка.

\begin{lstlisting}[language=Python,caption=smoothnessCalculationReducer.py, label=lst:SCR]
(last_key, values) = (None, None)
Abbrs=[]
SSs=[]
maxTi = sys.float_info.min
minTi = sys.float_info.max
print "KEY, AVG_SS, AVG_ABBR, MIN_TI, MAX_TI"
for line in sys.stdin:
    (key, values) = line.strip().split("\t")   
    if last_key and last_key != key:
        print "%s, %f, %f, %f, %f" % (last_key, numpy.mean(SSs), numpy.mean(Abbrs), minTi, maxTi)
        Abbrs=[]
        SSs=[]
        maxTi = sys.float_info.min
        minTi = sys.float_info.max
    values = values.split(" ")
    SS=float(values[0])
    Abbr=float(values[1])
    Ti = float (values[2])  
    if (Ti < minTi): minTi = Ti
    if (Ti > maxTi): maxTi = Ti 
    Abbrs.append(Abbr)
    if not isnan(SS) and SS > 0:
        SSs.append(SS)      
    last_key = key
if last_key:
    print "%s, %f, %f, %f, %f" % (last_key, numpy.mean(SSs), numpy.mean(Abbrs), minTi, maxTi)
 \end{lstlisting}
 
 
 




\section{Објектно-оријентисани дизајн и анализа}

\subsection{Увод}
Кључни део алгоритма за израчунавање глаткости се одвија при извођењу задатка за мапирање. Видели смо да задатак за мапирање, поред метода из \textit{graph6} пакета, користи неке специјално написане класе. Објаснићемо дизајн и улогу ових класа. Слика \ref{fig:UML} садржи \textit{UML} дијаграм ових класа. Треба приметити да задатак за редуковање нема никакву зависност од других класа, што је и логично, јер он само рачуна просечне вредности за структурну осетљивост и макслимални отклон  и максималну и минилану вредност тополошког индекса.

\begin{figure}[htp]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/ClassDiag.png}
\end{center}
\caption{UML дијаграм}
\label{fig:UML}
\end{figure}


\subsection{\textit{GraphGroup}}
На Слици \ref{fig:UML} се уочава апстрактна класа \textit{GraphGroup}, која има две подкласе: \textit{GraphGroupDraw} и \textit{GraphGroupMath}. Овакав дизајн је у складу са принципoм једне одговорности(\textit{SRP - Single Responsibillity Principle}) у објектно-оријентисаном моделу, који каже да класа треба да има само једну функционалност \cite{unclebob}. На овај начин се минимизује потреба за честом изменом класа што зна да буде велики проблем у софтверском инжењерству.

Класа \textit{GraphGroup} садржи два атрибута: листу графова и хеш табелу вредности испитиваних тополошких индекса за сваки од графова. Клaса такође садржи методе за додавање графова и рачунања вредности за један тополошки индекс. Листинг \ref{lst:GG} приказује имплементацију класе.

\begin{lstlisting}[language=Python,caption=GraphGroup.py, label = lst:GG]
class GraphGroup:
    
    def __init__(self):
        self.graphs = []
        self.Tis=dict()
        
    def addGraph(self, graph):
        self.graphs.append(graph)
        
    def count(self):
        return len(self.graphs)
    
    def calculateTi(self, topologicalIndex):
        name = topologicalIndex.name()
        values=[] 
        for graph in  self.graphs:
            Ti = topologicalIndex.value(graph)
            values.append(Ti)        
        self.Tis[name]=values   
        return self.Tis 
\end{lstlisting}


У ранијим фазама истраживања јавила се потреба за генерисањем разноразних дијаграма над групом графова како би се олакшала анализа података. У ту сврху је направљена класа  \textit{GraphGroupDraw}.

\begin{lstlisting}[language=Python,caption=GraphGroupDraw.py, label=lst:GGD]
class GraphGroupDraw(GraphGroup):
    
    def drawGraphs(self, directory):
        if not path.exists(directory):
            mkdir(directory)
        index=0
        for graph in self.graphs:
            draw_spring(graph)
            plt.savefig("%s/%snew.png"%(directory, str(index)))
            index += 1 
            plt.clf()            
            
    def drawTiHistogram(self, directory, topologicalIndex):
        if not path.exists(directory):
            mkdir(directory)
        indexName = topologicalIndex.name()
        vector = robjects.FloatVector(self.Tis[indexName]) 
        imageName = "%s/%s.png" % (directory, indexName)
        robjects.r.png(imageName, width = 400 , height = 300)
        robjects.r.hist(vector, main = indexName,xlab="", col="lightblue")
        robjects.r('dev.off()')
        
 \end{lstlisting}
 
Kласа  \textit{GraphGroupDraw}. садржи методе за цртање свих графова у групи коришћењем методa из \textit{NetworkX} библиотеке. Такође, коришћењем R метода могуће је цртати хистограм за вредности тополошких индекса. Листинг \ref{lst:GGD} приказује имплементацију класе.

 

Класа \textit{GraphGroupMath} садржи методе за математичке прорачуне над групом графова. Тренутно су имплементиране статистичке методе за рачунање стандардне девијације и квартила за вредности тополошких индекса, као и метода за рачунање релативне разлике вредности тополошких индекса у односу на тополошки индекс тог графа. Ова класа се ослања на функционалности \textit{R} програмског језика што је могуће у \textit{Python}-у. Листинг \ref{lst:GGM} приказује имплемнтацију класе.
 

\begin{lstlisting}[language=Python,caption=GraphGroupMath.py, label = lst:GGM]
class GraphGroupDraw(GraphGroup):
    
    def drawGraphs(self, directory):
        if not path.exists(directory):
            mkdir(directory)
        index=0
        for graph in self.graphs:
            draw_spring(graph)
            plt.savefig("%s/%snew.png"%(directory, str(index)))
            index += 1 
            plt.clf() 
            
            
    def drawTiHistogram(self, directory, topologicalIndex):
        if not path.exists(directory):
            mkdir(directory)
        indexName = topologicalIndex.name()
        vector = robjects.FloatVector(self.Tis[indexName]) 
        imageName = "%s/%s.png" % (directory, indexName)
        robjects.r.png(imageName, width = 400 , height = 300)
        robjects.r.hist(vector, main = indexName,xlab="", col="lightblue")
        robjects.r('dev.off()')
               
\end{lstlisting}
 



\subsection{\textit{TopologicalIndex}}

Класа \textit{TopologicalIndex} служи за представљање тополошког индекса. Познато је да тополошки индекс рачунамо на следећи начин:

\begin{equation}
TI(G) = \sum_{(u,v) \in E(G)} F(d_u, d_v)
\nonumber
\end{equation}

Дакле, сваки индекс има специфичну функцију над степенма чворова. Овде је искоришћена функионалност \textit{Python}-а која омогућава да се фунцкија може доделити као вредност некој варијабли или атрибуту класе. 

\begin{lstlisting}[language=Python,caption=TopologicalIndex.py, label = lst:TI]
class TopologicalIndex:
    
    def __init__(self, function):
        self.function = function
        
    def value(self, graph):
        s = 0
        for edge in graph.edges():
            du = len(graph.neighbors(edge[0]))
            dv = len(graph.neighbors(edge[1]))
            s += self.function(float64(du), float64(dv))
        return s
    
    def name(self):
        return self.function.__name__
 \end{lstlisting}

Класа \textit{TopologicalIndex} дакле може да рачуна вредност индекса тако што пронађе суму вредности додељене фунцкије над степенима свих парова суседних чворова у графу. Листинг \ref{lst:TI} приказује имплементацију класе. 


\begin{lstlisting}[language=Python,caption=indexFunctions.py, label=lst:IF]
def R(du, dv): return 1 / (sqrt(du * dv))
def M1(du, dv): return du + dv
def M2(du, dv): return du * dv
def ABC(du, dv): return sqrt((du + dv - 2) / (du * dv))
def SCI(du, dv): return 1 / (sqrt(du + dv))
def GA1(du, dv): return 2 * sqrt(du * dv) / (du + dv)
def AZI(du, dv): return  power((du * dv) / (du + dv - 2), 3) 
def HI(du, dv): return 2 / (du + dv)
\end{lstlisting}
 
Све функције индекса које су у током истраживања биле испитивани се налазе у посебном фајлу. За испитивање новог тополошког индекса је потребно само дефинисанити нову фунцкију. Листинг \ref{lst:IF} показује садржај тог фајла.

\subsection{\textit{GED1GroupGenerator}}


Уколико погледамо \textit{UML} дијаграм класе \textit{GED1GroupGenerator} видимо да се неке фунцкионалности делегирају интерфејсу за генерисање јединственог идентификатора графа. Ово је комплексна функционалност и о томе ће бити више речи у следећем одељку. Оно што је сада битно уочити је да је класа дизајнирана у складу са пројектним обрасцем по имену \textit{Strategy} \cite{unclebob}. На овај начин класа постаје независна од имплементације интерфејса тако да може да ради са више типова генератора јединственог идентификатора, што је добро у случају евентуалног проширивања истраживања на друге типове графова. 

При дизајну класе, коришћен је и такозвани \textit{dependency injection} принцип. Тиме је класа ослобођена од било каквог управљања класом за генерисање јединственог идентификатора. Идеја је да се класи \textit{GED1GroupGenerator} једноставно проследи референца на инстанцу генератора, док ће неки контејенр водити рачуна о самом генератору. 



\section{Провера изоморфизма у линеарном времену}

\subsection{Увод}
Провера изоморфизма графова се показала као изазован проблем у току истраживања. Конреткно се мисли на проверу да ли је неки граф изоморфан са било којим елементом из неког скупа графова. У Алгоритму \ref{alg:ssabbr} смо показали да је овај поступак неопходан за генерисање групе графова који су структурно слични неком графу. 

У ранијој верзији софтвера за упоређивање графова коришћен је метод \textit{is\_isomorhic} из \textit{Networkx} пакета. Овај метод користи \textit{VF2} алгоритам за проверу изоморфизма, чија временска комплексност варира између $O(n^2)$ и $O(n!n)$ \cite{skiena}. Овај метод проверава изоморфизам два графа. Да би проверили да ли је неки граф изоморфан са било којим елементом из неког скупа графова, неопходно је итерирати кроз тај скуп и сваки његов елемент понаособ упоредити са испитиванм графом уз помоћ \textit{is\_isomorhic} методa. Овакво решење се показало као врло неефикасно.

Да би се решење убрзало, осмишљен је оригиналан начин за генерисање \textit{GED=1} скупа. Опште позната чињеница у свету алгоритама је да хеш мапе предтављају стрктуру података која омогућава брз начин за претрагу података \cite{skiena}. Стављањем информација о тополошкој структури графа у хеш мапе наш програм би био знатно убрзан. Тачније, уколико је на јединствен начин могуће обележити тополошку структуру неког графа, провера изоморфизма графа са елементима неког скупа графова би се једноставно свела на претрагу хеш мапе. За граф чије се тополошко обележје не налази у хеш табели закључујемо да није изоморфан ни са једним елементом скупа графова. Такав граф можемо да додамо у тај скуп, а самим тим и његово тополошко опбележје у хеш мапу.

Дакле, оригинални приступ решавања проблема генерисања \textit{GED=1} скупа састоји се из проналаска тополошког обележја графа и убрзања провере изоморфизма коришћењем хеш мапи.
Конкретно у нашем случају, било је потребно наћи начин за одређивање тополошког обележја некоренских стабала.


\subsection{Тополошко обележавање коренског стабла}

Као што смо већ поменули, наше истраживање се своди на класе стабала са истим бројем чворова. Познато је да постоје алгоритми који врше тополошко обележавање коренских стабала у линеарном времену \cite{marthe}. Дакле, наш проблем се може решити имплементацијом једног од ових алгоритама и употребом хеш мапа за чување тополошких вредности, под условом да постоји начинн за трансформацију некоренских стабала у коренска. Алгоритам \ref{alg:lbl} приказује како се може извршити тополошко обележавање једног коренског стабла.

\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}
\Fn(\tcc*[h]{recursive function}){Label(node)}{
\textit{subtreeLabel} ← []\;
\textit{number←Length(node.children)}\;
\If{number == 0}{
	\textbf{return} 0
}

\textit{children} ← \textit{node.children}\;
\For{ child in children }{
\textit{subtreeLabels.add(Label(child))}
}
\textit{Sort(subtreeLables)}\;

\textbf{return} (\textit{number + ',' + subtreeLabels.joinWith(',')})\;
}
\caption{Тополошко обележавање коренског стабла} 
\label{alg:lbl}
\end{algorithm}


Уочава се да је у алгоритму искорошћен такозвани метод подели-и-освоји који је рекурзивног типа. Слика \ref{fig:lbl} приказује како тече процес обележавања графа. Треба уочити како се (због рекурзивног својства алогоритма) процес изводи од листова ка корену.


\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=120mm]{images/label.png}
\end{center}
\caption{Тополошко обележавање коренског стабла}
\label{fig:lbl}
\end{figure}


Посматрајући алгоритам можемо уочити да се тополошко обележје коренског стабла предтавља као стринг састављен из: броја чворова који су директни потомци корена стабла, и лексикографски сортираних обележја свих подстабала са кореном у чвору који је директан потомак корена тог стабла. Стабло састављено из једног чвора има обележје 0. Сортирањем обележја се занемарује утицај редоследа потомака корена на тополошко обележје стабла, што предствавља кључну ствар код провере изоморфизма. Лако се уочава да алгоритам има линерану комплексност.



\subsection{Трансформација у коренскo стаблo}

У претходном делу је објашњен алгоритам за тополошко обележавање коренског стабла. Овај алгоритам се, међутим, може употребити на некоренским стаблима, што је потребно за израчунавање глаткости индекса \cite{marthe}. Некоренска стабла можемо лако трансформисати у коренска избором одговарајућег чвора за корен стабла. Да би валидно проверавали изоморфизам графова неопходно је наћи начин за одабир јединственог чвора за корен стабла тј. да за два изоморфна стабла увек изаберемо исти чвор као корен. 

На основу претходног објашњења тополошко обележје некоренског стабла се израчунава на следећи начин:

\begin{itemize}
\item Уколико у стаблу постоји један чвор са максималним степенoм, тополошко обележје тог стабла одговара тополошком обележју коренског стабла са кореном у чвору са максималним бројем степена.
\item Нека je $K(u)$ скуп повезаних компоненти графа који настаје када се из стабла уколни неки чвор $u$. Нека је $S$ скуп чворова такав да важи:
\begin{equation}
S = \{u \in V :\;  (\forall K \in K(u): |K| \leq \frac{|V|}{2}) \}
\end{equation}
Уколико за стабло које испитујемо скуп $S$ садржи један елемент, тополошко обележје тог стабла одговара тополошком обележју коренског стабла са кореном у једином елементу скупа $S$.
\item Уколико за стабло које испитујемо, претходно дефнисани скуп $S$ садржи два елемента (што се дешава у појединим случајевима код стабала са парним бројем чворова), тополошко обележје тог стабла одговара лексикографски мањем од два тополошка обележја коренских стабала са коренима у елементима скупа $S$.
\end{itemize}

Да би процес провере изоморфизма имао линеарну комплексност потребно је да претходно описан поступак има линеарну комплексност. Генерисање тополошког обележја стабла и тражење чворова са максималним степеном су процеси са линеарном комплексношћу. Потребно је објаснити како се у линеарном времену генерише скуп $S$. 


Да бисмо генерисали скуп $S$, наше стабло прво претварамо у коренско, произвољним избром чвора који преставља корен. Нека са $w(u)$ обележимо тежину подстабла, односно број елемената у подстаблу испитиваног стабла, са кореном у чвору $u$. Након тога примењујемо Алгоритам \ref{alg:weigh} за проналажење скупа $S$.

Алгоритам \ref{alg:weigh}, дакле, тражи чвор који би при избацивању из стабла поделио стабло на више компоненти од којих ниједна не би имала више од $\frac{n}{2}$ чворова, где је $n$ број чворова стабла. Очигледно је да овај алгоритам има линерану комплексност, тако да је сада могуће имплементирати алгоритам за проверу изоморфности који има линеарну комплексност.



\SetKwProg{Fn}{def}{\string:}{}
\begin{algorithm}[H]
\Fn(\tcc*[h]{recursive function}){Shift(u)}{
\If{$\neg\exists v: (u,v) \in E \wedge w(v)> \frac{n}{2}$ }{
\Return \{u\}\;
}
\ElseIf{$\exists v: (u,v) \in E \wedge w(v) = \frac{n}{2}$}{
\Return \{u,v\}\;
}
\Else{
$v \leftarrow w: (w,u) \in E \wedge w(w) > \frac{n}{2} $\;
$w(u) = w(u) - w(v)$\;
$w(v)= w(u)+w(v)$\;
\Return \textit{Shift(v)}\;
}
}
\caption{Тражење тежинског центра стабла} 
\label{alg:weigh}
\end{algorithm}
\vspace{5mm}

Слика \ref{fig:weigh}. показује како се врши прерачунавање тежина чворова при процесу избора новог корена стабла.

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width=150mm]{images/shift.png}
\end{center}
\caption{Тражење тежинског центра стабла}
\label{fig:weigh}
\end{figure}

\subsection{Имплементација линеарног алгоритма за проверу изоморфизма графова}

Листинг \ref{lst:GED1}  садржи део имплементације класе за генерисање групе графова која је структурно најсличнија неком графу. Треба уочити на који начин је имплементиран процес генерисања групе графова. Класа као атрибут има референцу на другу класу за генерисање тополошког обележја графа. У конструктору класе се прослеђује референца на инстанцу класе за генерисање тополошког обележја. Имплементација те класе је непозната, тако да то може да буде класа за генерисање тополошког обележја стабла или било које друге врсте графа.


\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.py, label=lst:GED1]
class GED1GroupGenerator:
    
    def __init__(self, thumbprintGenerator):
        self.thumbprintGenerator = thumbprintGenerator
        
    def setCodeGenerator(self, thumbprintGenerator):
        self.thumbprintGenerator = thumbprintGenerator
\end{lstlisting}

Класа има један метод за генерисање групе графова. Ова метода, премештањем грана стабла конструише све графове који су потенцијални чланови групе. Тополошка обележја чланова групе се чувају у хеш мапи. За сваки од конструисаних графова се проверава да ли је његово обележје у хеш мапи и уколико није, граф се додаје у групу. Листинг \ref{lst:GED1Gr} приказује имплементацију ове методе.


\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.generateGED1Group, label=lst:GED1Gr]       
    def generateGED1Group(self, graph):
        group = []   
        addedGraphs=dict()
        initialThumbprint=self.thumbprintGenerator.generateThumbprint(graph)
        for node in graph.nodes():  
            for neighobor in graph.neighbors(node):
                for nonNeighbor in non_neighbors(graph, node):
                    newGraph = graph.copy()
                    newGraph.remove_edge(node, neighobor)
                    newGraph.add_edge(node, nonNeighbor)            
                    if is_connected(newGraph):
                        thumbprint = self.thumbprintGenerator.generateThumbprint(newGraph)
                        if (thumbprint != initialThumbprint) and (thumbprint not in addedGraphs):
                            addedGraphs[thumbprint] = len(group)
                            group.append(newGraph)       
        return group 
\end{lstlisting}

За наш проблем је имплементирана класа за генерисање тополошких обележја некоренских стабала. У даљем истраживању се може нпр. направити класа за генерисање тополошких обележја других врста графова.

Листинг \ref{lst:thumb} приказује имплементацију метода за генерисање тополошког обележја стабла. Прво се одреде корени стабала. У неким ситуацијама код стабала са парним бројем чворова, као што је објашњено, не можемо јединиствено одредити чвор који би представљао корен стабла. За један или два чвора које пронађемо као корен, врши се тополошко обележавање, и као резултат се враћа лексикографски мање тополошко обележје.


\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.generateThumbprint, label = lst:thumb]
    def generateThumbprint(self,graph):
        roots = self.findRoots(graph)
        codes=[]
        for root in roots:
            tree=bfs_tree(graph,root)
            code=self.treeCode(tree, root)
            codes.append(code)
        codes=sorted(codes)
        return codes[0]
 \end{lstlisting}


Листинг \ref{lst:weigh} показује имплементацију методе за мерење тежине стабла, тј. бројање чворовова у подстаблима стабла. Овај метод је потребан за имплементацију алгоритма \ref{alg:weigh}. 

\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.weighNodes, label= lst:weigh]
	def weighNodes(self, tree, node, parent):     
        total = 1 
        children = [neighbor for neighbor in tree.neighbors(node) if neighbor != parent]
        for neighbor in children:
                    total += self.weighNodes(tree, neighbor, node)
        tree.node[node]["weight"] = total
        return total    

\end{lstlisting}

Листинг \ref{lst:shift} приказује имплементацију алгоритма \ref{alg:weigh} за избор корена 

\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.shift, label= lst:shift]    
    def shift(self,graph, currentNodeId):
        neighbors  = graph.neighbors(currentNodeId)
        for neighborId in neighbors:     
            if graph.node[neighborId]["weight"] > (graph.number_of_nodes() / 2.0):
                graph.node[currentNodeId]["weight"] -= graph.node[neighborId]["weight"]
                graph.node[neighborId]["weight"] += graph.node[currentNodeId]["weight"]
                return self.shift(graph, neighborId)
            elif graph.node[neighborId]["weight"] == (graph.number_of_nodes() / 2.0):
                return [currentNodeId, neighborId]
        return [currentNodeId]
\end{lstlisting}

Листинг \ref{lst:root} показује метод за избор чвора коренског стабла, тако што се, уколико не постоји јединствени чвор са максималним бројем чворова, позива имплементација алгоритма \ref{alg:weigh}.

\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.findRoots, label= lst:root]        
    def findRoots(self,graph):        
        degrees = graph.degree().values()
        maximum=max(degrees)
        count=degrees.count(maximum)
        if count == 1:
            return [degrees.index(maximum)]
        else:
            self.weighNodes(graph, 0, -1)
            return self.shift(graph, 0)

\end{lstlisting}





Листинг \ref{lst:treeCode} садржи имплементацију Алгоритма \ref{alg:lbl} за генерисање тополошког обележја коренског стабла. 

\begin{lstlisting}[language=Python,caption=GED1GroupGenerator.treeCode, label=lst:treeCode]
  def treeCode(self,tree, node): 
        neighbors = tree.neighbors(node)
        subtreeLabels=[]
        for neighbor in neighbors:
            subtreeLabels.append(self.treeCode(tree, neighbor))
            
        sortedSubtreeLabels=sorted(subtreeLabels)
        
        if len(neighbors) == 0: 
            return str(len(neighbors))
        else: 
            return str(len(neighbors)) + "," + ",".join(sortedSubtreeLabels)
 \end{lstlisting}



\chapter{Анализа резултата}
\section{Скалирање софтвера}
\subsection{Резултати}
Паралелни софтвер за испитивање глаткости тополошких индекса, описан у претходном поглављу, је покренут на делу кластера КРАГУЈ ПМФ-а у Крагујевцу. За потребе извршавања софтвера коришћене су два рачунарска чвора који су на располагању имала по 4 процесорске јединице и по један физички хард диск. 

За проверу скалабилности софтвера извршени су послови испитивања глаткости тополошких индекса на класи стабала од 15 чворова. 

У Табели \ref{tbl:scall} је представљена зависност времена извршавања посла у односу на број \textit{Hadoop} процеса покренутих на кластеру за извршавање задатака за мапирање и редуковање. Исти однос је представљен и Дијаграмом \ref{fig:scall}, како би се лакше уочио интензитет убрзања софтвера.

\vspace{10px}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 140mm]{images/scall.png}
\end{center}
\caption{График скалабилности софтвера}
\label{fig:scall}
\end{figure}

\begin{table}[h]
\centering
\caption{Скалирање софтвера}
\begin{tabular}{c c}
Број задатака &  Време извршавања(\textit{sec}) \\
\hline
4 &1288 \\
8 &	726 \\
16	& 522 \\
32	& 586 \\

\end{tabular}
\label{tbl:scall}
\end{table}

\subsection{Дискусија}

Напоменимо да је током извршавања посла било доступно 8 физичких процесорских јединица. На графику уочавамо значајно убрзање програма када је број \textit{Hadoop} процеса за задатке мапирања и редуковања повећан са 4 на 8. Ово је последица једноставног искоришћавања свих доступних процесорских јединица. Иако је број  искоришћених процесора двоструко већи, не добијамо пропорционално убрзање. Ово је последица чињенице да је додатно процесорско време потребно за управљање већим бројем процеса.

\textit{Hadoop} процеси интензивно обављају улазно-излазне операције. Због блокирајућег својства ових операција, пожељно је покренути више \textit{Hadoop}  процеса по једној процесорској јединици \cite{hadoop}. На тај начин се добија боље искоришћење процесора, јер се време у ком један процес чека на улаз/излаз може искористити за извршавање другог процеса. На графику уочавамо додатно убрзање уколико се покрену два процеса по једној физичкој процесорској јединици.


Даљим повећањем на 4 процеса по једној физичкој процесорској јединици добијамо успоравање програма. Ово је последица чињенице да приемпција процеса користи много више процесорског времена.


\section{Анализа глаткости испитиваних индекса}
\subsection{Резултати}
Извршавањем програма добијени су резултати који нам дају бољи увид у квалитет тополошког индекса са аспекта глаткости. 

У предстојећим табелама представљене су добијене вредности за структурну осетљивост и максимални отклон, као и максималне и минималне вредности тополошког индекса у испитиваној класи стабала. На дијаграмима који су приказани показан је процентуални однос структурне осетљивости и максималног отклона у односу на опсег вредности тополошког индекса (разлика максималне и минималне вредности индекса). 

Разлог приказивања процентуалног односа  структурне осетљивости и максималног отклона је тај што на таj начин можемо упоређивати различите индексе на истој скали. Наиме, структурна осетљивост и максимални отклон су апсолутне величине, које за различите индексе имају доста различите вредности, тако да је немогуће упоредити њихове апсолутне величине.

Приказани су резултати за стабла са 6, 10, 15, 16, 18 и 20 чворова. 




\newpage

\begin{table}[H]
\centering
\caption{Резултати за стабла са 6 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS} &\textit{ABBR}  \\
\hline
\textit{ABC}&0.2144&0.3419&3.5355&4.4721&0.9366&22.90\%&36.51\%\\
\textit{AZI}&7.2752&11.3232&9.7656&40.0000&30.2344&24.06\%&37.45\%\\
\textit{GA1}&0.2495&0.3984&3.7268&4.8856&1.1588&21.53\%&34.38\%\\
\textit{HI}&0.2574&0.4056&1.6667&2.8333&1.1667&22.06\%&34.76\%\\
\textit{M1}&3.0586&4.0000&18.0000&30.0000&12.0000&25.49\%&33.33\%\\
\textit{M2}&2.2568&3.3333&16.0000&25.0000&9.0000&25.08\%&37.04\%\\
\textit{R}&0.1472&0.2359&2.2361&2.9142&0.6781&21.70\%&34.79\%\\
\textit{SCI}&0.1324&0.2104&2.0412&2.6547&0.6135&21.58\%&34.29\%\\
\end{tabular}
\end{table}


\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res6.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 6 чворова}
\end{figure}




\newpage


\begin{table}[H]
\centering
\caption{Резултати за стабла са 10 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS}&\textit{ABBR} \\ 
\hline
\textit{ABC}&0.1861&0.3808&6.3235&8.4853&2.1618&8.61\%&17.62\%\\
\textit{AZI}&6.0732&12.6171&12.8145&75.3906&62.5762&9.71\%&20.16\%\\
\textit{GA1}&0.2536&0.4797&5.4000&8.8856&3.4856&7.27\%&13.76\%\\
\textit{HI}&0.2442&0.4580&1.8000&4.8333&3.0333&8.05\%&15.10\%\\
\textit{M1}&3.4278&6.0566&34.0000&90.0000&56.0000&6.12\%&10.82\%\\
\textit{M2}&4.5617&9.8962&32.0000&81.0000&49.0000&9.31\%&20.20\%\\
\textit{R}&0.1434&0.2733&3.0000&4.9142&1.9142&7.49\%&14.28\%\\
\textit{SCI}&0.1352&0.2494&2.8461&4.6547&1.8087&7.48\%&13.79\%\\
\end{tabular}
\end{table}



\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res10.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 10 чворова}
\end{figure}







\newpage

\begin{table}[H]
\centering
\caption{Резултати за стабла са 15 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS}&\textit{ABBR}\\
\hline
\textit{ABC}&0.1653&0.4044&9.7763&13.4907&3.7145&4.45\%&10.89\%\\
\textit{AZI}&6.2548&15.9034&17.4857&123.6480&106.1623&5.89\%&14.98\%\\
\textit{GA1}&0.2330&0.5231&6.9844&13.8856&6.9012&3.38\%&7.58\%\\
\textit{HI}&0.2216&0.4858&1.8667&7.3333&5.4667&4.05\%&8.89\%\\
\textit{M1}&3.4542&7.1327&54.0000&210.0000&156.0000&2.21\%&4.57\%\\
\textit{M2}&5.7591&15.3315&52.0000&196.0000&144.0000&4.00\%&10.65\%\\
\textit{R}&0.1299&0.2942&3.7417&7.4142&3.6726&3.54\%&8.01\%\\
\textit{SCI}&0.1250&0.2695&3.6148&7.1547&3.5399&3.53\%&7.61\%\\
\end{tabular}
\end{table}

\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res15.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 15 чворова}
\end{figure}


\newpage



\begin{table}[H]
\centering
\caption{Резултати за стабла са 18 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS}&\textit{ABBR}\\
\hline
\textit{ABC}&0.1590&0.4130&11.8360&16.4924&4.6564&3.41\%&8.87\%\\
\textit{AZI}&6.4255&17.9321&20.3909&158.5176&138.1267&4.65\%&12.98\%\\
\textit{GA1}&0.2253&0.5392&7.7881&16.8856&9.0975&2.48\%&5.93\%\\
\textit{HI}&0.2140&0.4961&1.8889&8.8333&6.9444&3.08\%&7.14\%\\
\textit{M1}&3.4286&7.5201&66.0000&306.0000&240.0000&1.43\%&3.13\%\\
\textit{M2}&6.0795&17.5550&64.0000&289.0000&225.0000&2.70\%&7.80\%\\
\textit{R}&0.1252&0.3022&4.1231&8.9142&4.7911&2.61\%&6.31\%\\
\textit{SCI}&0.1212&0.2769&4.0069&8.6547&4.6478&2.61\%&5.96\%\\
\end{tabular}
\end{table}


\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res18.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 18 чворова}
\end{figure}






\newpage

\begin{table}[H]
\centering
\caption{Резултати за стабла са 19 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS}&\textit{ABBR}\\
\hline
\textit{ABC}&0.1574&0.4155&12.5378&17.4929&4.9551&3.18\%&8.39\%\\
\textit{AZI}&6.4751&18.5793&21.3670&172.1181&150.7512&4.30\%&12.32\%\\
\textit{GA1}&0.2234&0.5440&8.0387&17.8856&9.8469&2.27\%&5.52\%\\
\textit{HI}&0.2121&0.4991&1.8947&9.3333&7.4386&2.85\%&6.71\%\\
\textit{M1}&3.4222&7.6321&70.0000&342.0000&272.0000&1.26\%&2.81\%\\
\textit{M2}&6.1595&18.2010&68.0000&324.0000&256.0000&2.41\%&7.11\%\\
\textit{R}&0.1240&0.3046&4.2426&9.4142&5.1716&2.40\%&5.89\%\\
\textit{SCI}&0.1203&0.2790&4.1295&9.1547&5.0252&2.39\%&5.55\%\\

\end{tabular}
\end{table}

\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res19.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 19 чворова}
\end{figure}






\newpage


\begin{table}[H]
\centering
\caption{Резултати за стабла са 20 чворова}
\begin{tabular}{l r r r r r r r}
\textit{TI}& \textit{AVG\_SS}& \textit{AVG\_ABBR}& \textit{MIN\_TI}& \textit{MAX\_TI}&\textit{RANGE}&\textit{SS}&\textit{ABBR}\\
\hline
\textit{ABC}&0.1561&0.4178&13.2111&18.4932&5.2822&2.95\%&7.91\% \\
\textit{AZI}&6.5215&19.2113&22.3459&196.1591&173.8133&3.75\%&11.05\%\\
\textit{GA1}&0.2217&0.5483&8.2819&18.8856&10.6037&2.09\%&5.17\%\\
\textit{HI}&0.2104&0.5018&1.9000&9.8333&7.9333&2.65\%&6.33\%\\
\textit{M1}&3.4168&7.7355&74.0000&380.0000&306.0000&1.12\%&2.53\%\\
\textit{M2}&6.2303&18.8074&72.0000&361.0000&289.0000&2.16\%&6.51\%\\
\textit{R}&0.1230&0.3068&4.3589&9.9142&5.5553&2.21\%&5.52\%\\
\textit{SCI}&0.1194&0.2810&4.2485&9.6547&5.4062&2.21\%&5.20\%\\


\end{tabular}
\end{table}

\vspace{20mm}

\begin{figure}[htb]
\begin{center}
\leavevmode
\includegraphics[width = 150mm, height=105mm]{images/res20.png}
\end{center}
\caption{Структурна осетљивост и максимални отклон за стабла са 20 чворова}
\end{figure}






\newpage


\subsection{Дискусија}

Посматрајући претходне дијаграме и табеле долазимо до одређених закључака.

Испитивање индекса на стаблима са малим бројем чворова даје врло непоуздане резултате. На стаблима са 6 чворова, можемо уочити да између индекса готово да нема разлика и да су вредности за структурну осетљивост врло велике. Даље, код стабала са 10 чворова уочавамо да однос индекса није конзистентан са осталим графовима. Ако упоредимо резулате код стабала са 15 чворова и више, уочава се одржавање односа између индекса.

Анализирајмо резулте на дијаграмима за стабла са већим бројем чворова. Уочавамо да индекс \textit{First Zagreb(M1)} има најбољу структурну осетљивост и најмањи максимални отклон, што доводи до закључка да је овај индекс најбољи са аспекта глаткости. 

Даље, можемо приметити да класични \textit{Randic(R)} индекс и два релативно скоро предложена индекса, \textit{Sum-connectivity(SCI)} и \textit{Geometric-arithmetic($GA_1$)} имају готово исте вредности за структурну осетљивост и максимални отклон. Поставља се питање да ли је увођење ових индекса заиста оправдано.

Индекс \textit{Second Zagreb(М2)} има готово исту вредност за структурну осетљивост као претходно наведена три индекса. Међутим, његов максимални отклон је доста већи, тако да је он мање квалитетан од остала три индекса. 

Као два најлошија индекса су се показали \textit{Atom-bond connectivity(ABC)} и \textit{Augmented Zagreb(АZI)}. Овакав резултат је у контрадикцији са тврдњама да \textit{ABC} индекс представља врло добру меру за термодинамичке особине алкана.




\chapter*{Закључак}

Циљ овог рада је био одређивање критеријума за мерење караткеристике молекулских структурних дескриптора, познатије као глаткост. Глаткост тополошког индекса је само једна од караткеристика коју тополошки индекс треба да поседује.

Као резултат рада, добјене су кватитативне вредности за глаткост одређених тополошких индекса. Међусобним упоређивањем индекса омогућен је бољи увид у квалитет и примењивост испитиваних тополошких индекса. Такође, показали смо колико је квалитетан софтвер неопходан за потпуно искоришћавање сирове рачунарске снаге добијене коришћењем дистрибуираних платформи. Oсмишљен је, и имплементиран оригиналан приступ за брзо упоређивање изоморфизма једног графа са елементима неког скупа графова. 

Може се навести и неколико смерница за будући рад на истраживању глаткости тополошких индекса графова. Извршавања софтвера у хетерогеном окружењу, на више кластера (нпр. коришћењем \textit{Diet} фрејмворка или сличног), би омогућило испитивање обимнијих проблема. Затим, проблем се са структурних дескриптора базираних на степенима чворова, може проширити и на друге типове дескриптора. Испитивање и других класа графова, осим стабала, би донело прецизније резултате о квалитету тополошких индекса.



\begin{thebibliography}{10}
\bibitem{gutman} {Иван Гутман, Увод у хемијску теорију графова, Крагујевац, 2003}
\bibitem{boris} {Борис Фуртула, On structure-sensitivity of degree-based topological indices, Крагујевац, 2013}
\bibitem{emc} { Digital Universe nn 2020, http://www.emc.com/collateral/analyst-reports/idc-the-digital-universe-in-2020.pdf, EMC, 2012}
\bibitem{hadoop} {Tom White, Hadoop: The definitive guide, O'Reilly Media, 2012}
\bibitem{dfscomp} {http://nmims.edu/wp-content/uploads/2012/p3/MPSTME/DFS\_ICAET2011.pdf, Review of Distributed File Systems}
\bibitem{nauty} {Nauty and Traces User's Guide, http://cs.anu.edu.au/people/bdm/nauty/nug.pdf, 2013}
\bibitem{networkx} {NetworkX Reference, http://networkx.github.io/documentation/development/\_downloads/ networkx\_reference.pdf, 2013}
\bibitem{skiena} {Steven Skiena, The Algorithm Design Manual, Springer, 2008}

\bibitem{unclebob} {Robert Martin, Agile Software Development, Principles, Patterns, and Practices , Prentice Hall, 2002}

\bibitem{marthe} {http://perso.ens-lyon.fr/eric.thierry/Graphes2010/marthe-bonamy.pdf, Small Report on Graph and Tree Isomorphism, 2010}


\end{thebibliography}

	
\end{document}


